。找出第 K 個最小對距離

719。求第 K 個最小對距離

難度：難

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

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

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

範例1：

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

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

那麼第一個^第最小距離對是(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

以上是。找出第 K 個最小對距離的詳細內容。更多資訊請關注PHP中文網其他相關文章！