数组中两个元素的第k个最小绝对差
原文： 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
上界是二分搜索的一种变体，它从a[i]到大于[a] + mid的a[n-1]返回指向第一个元素的指针。 让返回的指针为j。 然后a[i] + mid < a[j]。 因此，从中减去a + i + 1将得到与a[i]的差为<= mid的值的数量。 我们对所有从 0 到n-1的索引求和，并得到当前中值的答案。
C++
// 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 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
# 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)。
版权属于：月萌API www.moonapi.com，转载请注明出处
