719。求第 K 個最小對距離

難度： 困難

主題： 陣列、兩個指標、二分查找、排序

整數對的距離定義為a和b之間的絕對差。

給定一個整數數組nums 和一個整數k，返回第k^th所有對 nums[i] 和nums[j] 中最小的距離，其中0 .

範例1：

• 輸入： nums = [1,3,1], k = 1
• 輸出： 0
• 解釋： 這是所有的對：

  (1,3) -> 2
  (1,1) -> 0
  (3,1) -> 2

則第1^第最小距離對為(1,1)，其距離為0。

範例2：

• 輸入： nums = [1,1,1], k = 2
• 輸出： 0

範例3：

• 輸入： nums = [1,6,1], k = 3
• 輸出： 5

約束：

• n == nums.length
• 2 4
• 0 6
• 1

暗示：

1. 二分找答案。如何檢查有多少對距離

解決方案：

我們可以結合使用二分查找和雙指標技術。這是解決此問題的逐步方法：

方法：

1. 將陣列排序：首先，將陣列 nums 進行排序。排序有助於有效計算距離小於或等於給定值的對的數量。

2. 距離二分查找：使用二分查找找到第 k 個最小距離。距離的搜尋空間範圍從 0（最小可能距離）到 max(nums) - min(nums)（最大可能距離）。

3. 計數距離 ≤ Mid 的對：對於二分查找中的每個 mid 值，計算距離小於或等於 mid 的對的數量。這可以使用兩指標方法有效地完成。

4. 調整二分查找範圍：根據距離小於或等於mid的對的數量，調整二分查找範圍。如果計數小於k，則增加下界；否則，減少上限。

讓我們用 PHP 實作這個解決方案：719。求第 K 個最小對距離

解釋：

• countPairsWithDistanceLessThanOrEqualTo：此函數計算有多少對距離小於或等於 mid。它使用兩個指針，其中right是當前元素，left調整直到nums[right]和nums[left]之間的差小於或等於mid。

• smallestDistancePair：此函數使用二分查找來找出第 k 個最小距離。低值和高值定義距離的目前搜尋範圍。使用 countPairsWithDistanceLessThanOrEqualTo 函數檢查中間值。根據結果調整搜尋空間。

此演算法有效地找出第 k 個最小的對距離，時間複雜度為 O(n log(max(nums) - min(nums)) n log n)。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給存儲庫 一顆星，或者在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub