数据结构：求解第k大（小）数

求解第k大（小）数

确定性算法与不确定性算法（随机化算法）

• 确定性算法： 第一次运行结果和第n次结果一致，不会受运行次数的影响。
• 随机化算法： 在算法中使用了随机函数，且随机函数的返回值直接或间接的影响了算法的执行流程或执行结果。而确定性算法是与随机化算法相对来说的 。

中位数排序 —— 类似快速排序的方法，目的得到第k小数（类似的有第k大数）

---

1. 确定性算法：方法1

理解如下：

代码如下：

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
	int findKthLargest(vector<int>& nums, int k)
	{
		int result = 0;
		int numsSize = int(nums.size());
		if (numsSize == 0 || k > numsSize)
		{
			return 0;
		}
		//寻找第kMIN小的数
		int kMin = numsSize - k + 1;
		result = select(nums, 0, numsSize - 1, kMin);
		return result;
	}

	int select(vector<int>& nums, int left, int right, int target)
	{
		if (left == right)
		{
			return nums[left];
		}
		int cut = partition(nums, left, right);
		//当前第currentResult小的元素
		int currentResult = cut - left + 1;
		if (target == currentResult)
		{
			return nums[cut];
		}
		else if (target < currentResult)
		{
			return select(nums, left, cut - 1, target);
		}
		else
		{
			//寻找接下来第target - currentResult小的数
			return select(nums, cut + 1, right, target - currentResult);
		}
		return 0;
	}
	
	int partition(vector<int>& nums, int left, int right)
	{
		int cut = nums[right];
		//i指向大堆的最左边的数，j指向下一个判断的数
		int i = left;
		for (int j = left; j < right; j++)
		{
			if (nums[j] <= cut)
			{
				exchange(nums[i], nums[j]);
				i++;
			}
		}
		exchange(nums[i], nums[right]);
		return i;
	}
	
	void exchange(int& a, int& b)
	{
		int tmpInt = a;
		a = b;
		b = tmpInt;
		return;
	}
};

int main()
{
	Solution solution = Solution();
	vector<int> arrays = { 33,22,10,45,67,8,6,23,4,78 };
	cout << solution.findKthLargest(arrays,3) << endl;

	return 0;
}

时间复杂度 : 平均情况 O(N)，最坏情况 O(N^2)
空间复杂度 : O(1)。

2.确定性算法：bfprt算法

借用别人的分析（太困了直接贴）：

在BFPTR算法中，仅仅是改变了快速排序Partion中的pivot值的选取，在快速排序中，我们始终选择第一个元素或者最后一个元素作为pivot，而在BFPTR算法中，每次选择五分中位数的中位数作为pivot，这样做的目的就是使得划分比较合理，从而避免了最坏情况的发生。算法步骤如下：

（1）将输入数组的 n 个元素划分为 n/5 组，每组5个元素，且至多只有一个组由剩下的 n%5 个元素组成。

（2）寻找 n/5 个组中每一个组的中位数，首先对每组的元素进行插入排序，然后从排序过的序列中选出中位数。

（3）对于（2）中找出的 n/5 个中位数，递归进行步骤（1）和（2），直到只剩下一个数即为这 n/5 个元素的中位数，找到中位数后并找到对应的下标 p。

（4）进行Partion划分过程，Partion划分中的pivot元素下标为 p。

（5）进行高低区判断即可。

本算法的最坏时间复杂度为 O(n)，值得注意的是通过BFPTR算法将数组按第K小（大）的元素划分为两部分，而这高低两部分不一定是有序的，通常我们也不需要求出顺序，而只需要求出前K大的或者前K小的。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

class Solution{
    class Solution
{
public:

	/* 快排思路 一次划分 */
	int quickpart(vector<int>& a, int l, int r, int pos)
	{
		int tmp = a[pos];
		a[pos] = a[l];
		a[l] = tmp;

		int pivot = a[l];
		int i = l;
		int j = r;
		while (i < j)
		{
			while (a[j] >= pivot && i < j)
				j--;
			a[i] = a[j];
			while (a[i] < pivot && i < j)
				i++;
			a[j] = a[i];
		}
		a[i] = pivot;
		return i;
	}

	/* bfprt 算法*/
	int bfprt(vector<int>& a, int l, int r, int k)
	{
		if (r - l + 1 <= 5) // 小于等于5个元素 直接排序输出结果
		{
			sort(a.begin() + l, a.begin() + r + 1);
			return a[l + k - 1];
		}

		//  1 首先把数组按5个数为一组进行分组，最后不足5个的忽略。对每组数进行排序（如插入排序）求取其中位数。
		//  2 把上一步的所有中位数移到数组的前面
		int t = l;
		int cnt = (r - l + 1) / 5;
		for (int i = 0; i < cnt; i++)
		{
			sort(a.begin() + l + i * 5, a.begin() + l + (i + 1) * 5);

			int tmp = a[l + i * 5 + 2];
			a[l + i * 5 + 2] = a[t];
			a[t] = tmp;

			t++;
		}
		t--;

		//  3 对这些中位数递归调用BFPRT算法求得他们的中位数
		int pos = (l + t) / 2; // l-t的中位数的下标， 中位数是第 pos - l + 1数
		bfprt(a, l, t, pos - l + 1); // 递归查找中位数的中位数,确保中位数在pos这个位置

		// 4 将上一步得到的中位数作为划分的主元进行整个数组的划分, 快排思路
		int m = quickpart(a, l, r, pos);

		// 5 判断第k个数在划分结果的左边、右边还是恰好是划分结果本身，前两者递归处理，后者直接返回答案。
		if (m - l + 1 == k)
			return a[m];
		else if (m - l + 1 < k)
			return bfprt(a, m + 1, r, k - (m - l + 1));
		else
			return bfprt(a, l, m - 1, k);;
	}

	int findKthLargest(vector<int>& nums, int k) {
		int len = nums.size();
		return bfprt(nums, 0, len - 1, len - k + 1);
	}
}
    
int main()
{
	Solution solution = Solution();
	vector<int> arrays = { 33,22,10,45,67,8,6,23,4,78 };
	cout << solution.findKthLargest(arrays,3) << endl;
	return 0;
}

本算法最坏时间复杂度为的证明可以参考《算法导论》9.3节

3. 不确定性算法（随机化算法）： 快速随机排序算法

#include <iostream>
#include <string>
#include<algorithm>
using namespace std;


int myrand(int p, int r)
{
	int size = r - p;
	return p + rand() % size;
}
void swap(int& a, int& b)
{
	int temp = b;
	b = a;
	a = temp;
}

int partition(int arr[], int p, int r)
{
	int x = arr[r];
	int i = p - 1;
	for (int j = p; j <= r - 1; j++)
	{
		if (arr[j] <= x)
		{
			i = i + 1;
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[i + 1], arr[r]);
	return i + 1;
}

int randomizedpartition(int arr[], int p, int r)
{
	int index = myrand(p, r);
	swap(arr[index], arr[r]);
	return partition(arr, p, r);
}

int randomizedselect(int arr[], int p, int r, int k)
{
	if (p == r) return arr[p];
	int q = randomizedpartition(arr, p, r);
	int m = q - p + 1;
	if (k == m) return arr[q];
	else if (k < m)
		return randomizedselect(arr, p, q - 1, k);
	else if (k > m)
		return randomizedselect(arr, q + 1, r, k - m);
}
int main()
{
	int array[10] = { 33,22,10,45,67,8,6,23,4,78 };
	cout << randomizedselect(array, 0, 9, 6) << endl;

	return 0;
}