數組中兩個元素的第 k 個最小絕對差 · GeeksForGeeks 中文系列教程

# 數組中兩個元素的第 k 個最小絕對差 > 原文： [https://www.geeksforgeeks.org/k-th-smallest-absolute-difference-two-elements-array/](https://www.geeksforgeeks.org/k-th-smallest-absolute-difference-two-elements-array/) 給定一個大小為`n`的數組，其中包含正整數。索引`i`和`j`處的值之間的絕對差為`|a[i] – a[j]|`。有`n * (n-1) / 2`個這樣的對，要求我們在所有這些對中打印第`k`個（`1 <= k <= n * (n-1) / 2`）最小的絕對差。 **示例**： ``` Input : a[] = {1, 2, 3, 4} k = 3 Output : 1 The possible absolute differences are : {1, 2, 3, 1, 2, 1}. The 3rd smallest value among these is 1. Input : n = 2 a[] = {10, 10} k = 1 Output : 0 ``` **樸素的方法**是找到`O(n ^ 2)`中所有`n * (n-1) / 2`個可能的絕對差并將它們存儲在數組中。然后對該數組進行排序，并打印該數組的第`k`個最小值。這將花費時間`O(n ^ 2 + n ^ 2 * log(n ^ 2)) = O(n ^ 2 + 2 * n ^ 2 * log(n))`。樸素的方法對于較大的`n`值（例如`n = 10 ^ 5`）不會有效。 **有效解決方案**基于二分搜索。 ``` 1) Sort the given array a[]. 2) We can easily find the least possible absolute difference in O(n) after sorting. The largest possible difference will be a[n-1] - a[0] after sorting the array. Let low = minimum_difference and high = maximum_difference. 3) while low < high: 4) mid = (low + high)/2 5) if ((number of pairs with absolute difference <= mid) < k): 6) low = mid + 1 7) else: 8) high = mid 9) return low ``` 我們需要一個函數，該函數可以有效地告訴我們差異< =中的對數。由于對數組進行了排序，因此可以像下面這樣完成此部分： ``` 1) result = 0 2) for i = 0 to n-1: 3) result = result + (upper_bound(a+i, a+n, a[i] + mid) - (a+i+1)) 4) return result ``` [上界](https://www.geeksforgeeks.org/binary-search-functions-in-c-stl-binary_search-lower_bound-and-upper_bound/)是二分搜索的一種變體，它從`a[i]`到大于`[a] + mid`的`a[n-1]`返回指向第一個元素的指針。讓返回的指針為`j`。然后`a[i] + mid < a[j]`。因此，從中減去`a + i + 1`將得到與`a[i]`的差為`<= mid`的值的數量。我們對所有從 0 到`n-1`的索引求和，并得到當前中值的答案。 ## C++ ```cpp // C++ program to find k-th absolute difference // between two elements #include<bits/stdc++.h> using namespace std; // returns number of pairs with absolute difference // less than or equal to mid. int countPairs(int *a, int n, int mid) { ????int res = 0; ????for (int i = 0; i < n; ++i) ????????// Upper bound returns pointer to position ????????// of next higher number than a[i]+mid in ????????// a[i..n-1]. We subtract (a + i + 1) from ????????// this position to count ????????res += upper_bound(a+i, a+n, a[i] + mid) - ????????????????????????????????????(a + i + 1); ????return res; } // Returns k-th absolute difference int kthDiff(int a[], int n, int k) { ????// Sort array ????sort(a, a+n); ????// Minimum absolute difference ????int low = a[1] - a[0]; ????for (int i = 1; i <= n-2; ++i) ????????low = min(low, a[i+1] - a[i]); ????// Maximum absolute difference ????int high = a[n-1] - a[0]; ????// Do binary search for k-th absolute difference ????while (low < high) ????{ ????????int mid = (low+high)>>1; ????????if (countPairs(a, n, mid) < k) ????????????low = mid + 1; ????????else ????????????high = mid; ????} ????return low; } // Driver code int main() { ????int k = 3; ????int a[] = {1, 2, 3, 4}; ????int n = sizeof(a)/sizeof(a[0]); ????cout << kthDiff(a, n, k); ????return 0; } ``` ## Java ```java // Java program to find k-th absolute difference // between two elements import java.util.Scanner; import java.util.Arrays; class GFG { ????// returns number of pairs with absolute ????// difference less than or equal to mid? ????static int countPairs(int[] a, int n, int mid) ????{ ????????int res = 0, value; ????????for(int i = 0; i < n; i++) ????????{ ????????????// Upper bound returns pointer to position ????????????// of next higher number than a[i]+mid in ????????????// a[i..n-1]. We subtract (ub + i + 1) from ????????????// this position to count? ????????????int ub = upperbound(a, n, a[i]+mid); ????????????res += (ub- (i-1)); ????????} ????????return res; ????} ????// returns the upper bound ????static int upperbound(int a[], int n, int value) ????{ ????????int low = 0; ????????int high = n; ????????while(low < high) ????????{ ????????????final int mid = (low + high)/2; ????????????if(value >= a[mid]) ????????????????low = mid + 1; ????????????else ????????????????high = mid; ????????} ????return low; ????} ????// Returns k-th absolute difference ????static int kthDiff(int a[], int n, int k) ????{ ????????// Sort array ????????Arrays.sort(a); ????????// Minimum absolute difference ????????int low = a[1] - a[0]; ????????for (int i = 1; i <= n-2; ++i) ????????????low = Math.min(low, a[i+1] - a[i]); ????????// Maximum absolute difference ????????int high = a[n-1] - a[0]; ????????// Do binary search for k-th absolute difference ????????while (low < high) ????????{ ????????????int mid = (low + high) >> 1; ????????????if (countPairs(a, n, mid) < k) ????????????????low = mid + 1; ????????????else ????????????????high = mid; ????????} ????????return low; ????} ????// Driver function to check the above functions ????public static void main(String args[]) ????{ ????????Scanner s = new Scanner(System.in); ????????int k = 3; ????????int a[] = {1,2,3,4}; ????????int n = a.length; ????????System.out.println(kthDiff(a, n, k)); ????} } // This code is contributed by nishkarsh146 ``` ## Python3 ```py # Python3 program to find? # k-th absolute difference? # between two elements? from bisect import bisect as upper_bound? # returns number of pairs with? # absolute difference less than? # or equal to mid.? def countPairs(a, n, mid):? ????res = 0 ????for i in range(n):? ????????# Upper bound returns pointer to position? ????????# of next higher number than a[i]+mid in? ????????# a[i..n-1]. We subtract (a + i + 1) from? ????????# this position to count? ????????res += upper_bound(a, a[i] + mid)? ????return res? # Returns k-th absolute difference? def kthDiff(a, n, k):? ????# Sort array? ????a = sorted(a)? ????# Minimum absolute difference? ????low = a[1] - a[0]? ????for i in range(1, n - 1):? ????????low = min(low, a[i + 1] - a[i])? ????# Maximum absolute difference? ????high = a[n - 1] - a[0]? ????# Do binary search for k-th absolute difference? ????while (low < high):? ????????mid = (low + high) >> 1 ????????if (countPairs(a, n, mid) < k):? ????????????low = mid + 1 ????????else:? ????????????high = mid? ????return low? # Driver code? k = 3 a = [1, 2, 3, 4]? n = len(a)? print(kthDiff(a, n, k))? # This code is contributed by Mohit Kumar? ``` 輸出： ``` 1 ``` 該算法的時間復雜度為`O(n * logn + n * logn * logn)`。排序需要`O(n * logn)`。之后，在低位和高位進行主要的二分搜索需要`O(n * logn * logn)`時間，因為每次對函數`int f(int c, int n, int * a)`的調用都需要時間`O(n * logn)`。