新数组中位数问题

问题描述

给定一个 N 个数的数组 cat[i]，并用这个数组生成一个新数组 ans[i]。新数组定义为对于任意的 i, j 且 i != j，均有 ans[] = abs(cat[i] - cat[j])，1 ≤ i < j ≤ N。试求出这个新数组的中位数，中位数即为排序之后 (len+1)/2 位置对应的数字，'/' 为下取整。

Input

多组输入，每次输入一个 N，表示有 N 个数，之后输入一个长度为 N 的序列 cat, cat[i] ≤ 1e9, 3 ≤ n ≤ 1e5

Output

输出新数组 ans 的中位数

Sample

Input: 
4
1 3 2 4
3
1 10 2
Output: 
1
8

Limitation

Time limit		1000 ms
Memory limit	65536 kB

解题思路

C题嘛，自然对时间复杂度要求严格，暴力求解会TLE，而且cin读入慢所以要采用scanf()。

产生的新数列全都不小于0，且原数列排序后cat[n - 1] - cat[0]一定是新数列中的最大数，也就是第n × (n - 1) / 2 - 1个，新数列排序后是单调递增的，而中位数就位于中间，因此可以对产生的新数进行二分：若新数的排名低于n × (n - 1) / 2，则它一定在中位数前面，若高于，则在后面，若等于，则就是所求的中位数。

问题来了，没有求出新数列，如何计算名次？
首先原数列是有序排列的，所以可以利用两个指针 i, j，j从第二位开始一直往后扫，同时i从第一位开始，一直扫到 j 的前面，计算cat[j] - cat[i]的值，如果大于目标数，则说明目标排名的后面有这个数，则可增加 i，求出最逼近目标排名的坐标，j - i 表示对于这个 j，目标之前一定有这么多个数在他前面；把所有可行的 j 遍历完后就可求出相对应的 j - i，这些 j - i 求和就是目标的名次。

港真，课上如果没说，真的很难想到这个层面……

源代码

#include <algorithm>
#include <cstdio>
using namespace std;

int Rank(int a, int* arr, int n) {
	int i = 1, rank = 0;
	for (int j = 2; j <= n; j++) {
		while (arr[j] - arr[i] > a)//对于每一个j, 求得距离
			i++;
		rank += (j - i);//这些距离之和就是名次
	}
	return rank;
}

int main() {
	int n;
	while (scanf_s("%d", &n) != EOF) {
		int* cat = new int[n + 10];
		for (int i = 1; i <= n; i++)
			scanf_s("%d", &cat[i]);//后面一直出问题 就索性从1开始记位
		sort(cat + 1, cat + n + 1);

		int N = n * (n - 1) / 2;//新数组的元素个数
		int begin = 1, end = cat[n];
		int aim = (N + 1) / 2;//目标中位数的位置，根据题意取的+1
		int middle = 0;
		while (begin <= end) {//二分求中位数
			middle = (begin + end) / 2;
			if (begin == end)
				break;
			int theRank = Rank(middle, cat, n);//当前名次
			if (theRank >= aim)//in the left
				end = middle;
			if (theRank < aim)//in the right
				begin = middle + 1;
		}
		printf("%d\n", middle);
	}
	return 0;
}