第K小的数和中位数

文章目录

1. 第K小的数和中位数

在一组有序数列中，如果数列大小是偶数，那么它的中位数是中间两数之和的一半；如果数列大小是奇数，那么它的中位数自然就是最中间的那个数。根据上面的定义，要得到有序数列的中位数，可以直接访问，复杂度是O(1)。

那如果给我们的数列是无序的呢？针对这个问题，我们可以再抽象一步，给定数值K，如果我们可以求得无序数列中第K小的数，那么求中位数就只需要第“中间”小的数了。当然这个中间需要根据上面的定义来确定K的值。

我们发现第K小的数的左边的数都比它小，后边都比它大。根据这个思路，我们想到可以利用快排的切分函数来进行求解。

快排切分函数

切分函数的想法我有两个，先讲百度百科的一个：

方法1

这个方法说的简单点就是挖坑、填坑。在数列两头设置两个扫描器，从两段向中间扫描，将数列的第一个数作为划分的目标数(target)，目的就是为了找到这个数的合适位置。

从尾到头扫，找到第一个比target小的数，放到从头开始的扫描器位置；接着从头到尾扫，找到第一个比target大的数，放到刚刚的那个指针的位置。这样说确实挺抽象的，那么我们来举个具体的例子就行了。

数列是2 4 9 3 6 7 1 5，头部扫描器从2扫到5，尾部扫描器从5扫到2，目标数是第一个数字2。

2 2 4 9 3 6 7 1 5 先从尾部扫描器开始，5比2大，扫描器向左，1比2小，将1放到头部扫描器的位置，原先1的位置就成坑了

2 1 4 9 3 6 7 1 5 头部扫描器开始，4比2大，将刚刚的坑（红色位置）填了

2 1 4 9 3 6 7 4 5 蓝色为头部扫描器的位置，绿色为尾部扫描器的位置。

2 1 4 9 3 6 7 4 5 继续从尾部扫描器开始，往前扫描，均大于目标数2，头部扫描器没有必要扫描了。最后一部，将target放到头部扫描器的位置。

经过划分得到最终结果：[1] 2 [4 9 3 6 7 4 5]。下面是伪代码：

partition(array,start,end)
	i = start; //头部扫描器
	j = end; //尾部扫描器
	target = array[start]; //目标数
	while(i<j)
		while(i<j && array[j] > target)
			j--;
		array[i] = array[j]; //挖坑
		while(i<j && array[i] < target)
			i++;
		array[j] = array[i]; //填坑
	End
	array[i] = target;
	return i;

方法2

需要用到交换函数，设置两个扫描器，一个i用来从头到尾遍历，另一个j用来表明划分的位置。

从头到底开始遍历，寻找第一个数的切分。如果找到比目标数小的数，那么将j往前进1，将i与j的元素交换。当扫描到底后，j的位置就是划分的位置。

partition(array, start,end)
	j = start;
	target = array[start];
	for(i=start+1;i<=end;i++)
		if(array[i]<target)
			j++;
			swap(array,i,j);
	array[j] = target;
	return j;

求第K小的函数

在找第K小的过程中，我们先对数列进行求划分，也就是对求出第一个数的划分。如果得到的索引就是k的位置，那么我们返回结果；如果得到的索引比K小，说明我们要找的数在这个索引的右边，start=partitionNumber+1；如果得到的索引比K大，说明我们要找的数在这个索引的左边，end=partitionNumber-1，下面是伪代码：

FindKthNumber(array,size,kth)
	start = 0;
	end = size-1;
	while(start<end)
		pivot = partition(array,start,end)
		if(pivot==kth)
			return array[pivot]
		else if(pivot<kth)
			start = pivot+1;
		else
			end = pivot+1;
	End

这样有了求第K小数的函数，我们可以根据定义得到中位数。

算法复杂度

因为求第K小的方法是每次对开头的数去进行切分，所以可以从概率的角度来进行分析。复杂度应该是O(n)的，我看了网上的分析，挺复杂的，也没有深入理解，所以只需要记住它是线性复杂度的就是了。

利用hash来求解第K小问题

在某天突然想到其实求第K小的数可以利用Hash来求得。先对数列进行Hash，接着设置计数器从最小的Hash开始访问，如果该位置没有，则继续访问；如果该位置有，计算有多少数据被Hash到这个位置上，加至计数器。从小到大访问Hash结构直到找到第K小的数。