Given N numbers, X1, X2, ... , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i ＜ j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!
Note in this problem, the median is defined as the (m/2)-th smallest number if m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of m = 6.
Input
The input consists of several test cases.
In each test case, N will be given in the first line. Then N numbers are given, representing X1, X2, ... , XN, ( Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )
Output
For each test case, output the median in a separate line.
Sample Input
4 1 3 2 4 3 1 10 2
Sample Output
1 8
题意：
给N数字, X1, X2, ... , XN，我们计算每对数字之间的差值：∣Xi - Xj∣ (1 ≤ i ＜ j ≤N). 我们能得到 C(N,2) 个差值，现在我们想得到这些差值之间的中位数。
如果总数m为偶数, 则为(m+1)/2。
思路：二分查找第k大值。
代码：
#include <iostream> #include <algorithm> #include <string.h> #include <cstdio> #include <string> #include <cmath> #include <vector> #include <stack> #include <queue> #include <stack> #include <list> #include <map> #include <set> //#include <unordered_map> #define Fbo friend bool operator < (node a, node b) #define mem(a, b) memset(a, b, sizeof(a)) #define FOR(a, b, c) for(int a = b; a <= c; a++) #define RFOR(a,b, c) for(int a = b; a >= c; a--) #define sc(a) scanf("%d",&a) #define off ios::sync_with_stdio(0) bool check1(int a) { return (a & (a - 1)) == 0 ? true : false; } using namespace std; typedef pair<int, int> pii; typedef long long ll; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const int Maxn = 2e5 + 5; const double pi = acos(-1.0); const double eps = 1e-8; int a[Maxn]; int n, m, l, r, mid; int solve(int mid) {//检验是否有m个 <= k的 | xi - xj | int cnt = 0;//统计小于mid的差有多少 FOR(i, 0, n - 1) { cnt += upper_bound(a, a + n, a[i] + mid) - a - i - 1; } int m = n * (n - 1) / 2;//C(n,2) m = (m + 1) / 2; return cnt >= m; } int main() { while (~sc(n)&&n) { FOR(i, 0, n-1) sc(a[i]); sort(a, a + n); l = 0, r = a[n-1]; while (l <= r) { mid = (l + r) >> 1; if (solve(mid)) { r = mid - 1; } else l = mid + 1; // cout << l << ‘ ‘ << r << endl; } printf("%d\n", l); } }
【POJ - 3579 】Median（二分）（查找第K大值）
原文：https://www.cnblogs.com/AlexLINS/p/12650558.html