数组中选出前K大的数（top K）

数组中选出前K大的数（top K）

此方法会打乱整个数组元素原本的顺序

基于partition函数基于快速排序中的partition函数，时间复杂度为O（n），空间复杂度为O（1）；需要改变输入；

（1）根据Partition函数得到索引值index，index前的数据均小于nums[index]，index后的数据均大于nums[index]

（2）如果index = k-1，则已经划分完成；数组前k个数据即为最大的k个数

（3）如果index>k-1，begin=index+1；否则end = index-1

（4）重复（2）操作直到index = k-1

#include <iostream>
#include <vector>

using namespace std;

int Partition(vector<int> &nums, int begin, int end)
{
	if (begin > end) return begin;
	int key = nums[begin];
	while (begin < end)
	{
		while (nums[end] <= key && begin < end)
		{
			--end;
		}
		nums[begin] = nums[end];
		while (nums[begin] > key && begin < end)
		{
			++begin;
		}
		nums[end] = nums[begin];
	}
	nums[begin] = key;
	return begin;
}

vector<int> getTopK(vector<int> nums, int k){
	if (nums.empty() || k > nums.size() || k <= 0) 
		return{};
	vector<int> ret;
	int begin = 0, end = nums.size() - 1;
	int idx = Partition(nums, begin, end);
	while (idx != k - 1)
	{
		if (idx < k - 1)
		{
			begin = idx + 1;

			idx = Partition(nums, begin, end);
		}
		else
		{
			end = idx - 1;
			idx = Partition(nums, begin, end);
		}
	}

	for (int i = 0; i < k; ++i) 
	{
		ret.push_back(nums[i]);
	}
	return ret;
}

int main()
{
	vector<int> nums{ 1, 2, 3, 4, 6, 9, 8 };
	vector<int> ret = getTopK(nums, 4);
	for (auto &index : ret)
	{
		cout << index << " ";
	}

	cout << endl;
	system("PAUSE");
	return 0;
}

数组中选出前K个小的数

#include <iostream>
#include <vector>

using namespace std;

int Partition(vector<int> &nums, int begin, int end)
{
	if (begin > end) return begin;
	int key = nums[begin];
	while (begin < end)
	{
		while (nums[end] >= key && begin < end)
		{
			--end;
		}
		nums[begin] = nums[end];
		while (nums[begin] <= key && begin < end)
		{
			++begin;
		}
		nums[end] = nums[begin];
	}
	nums[begin] = key;
	return begin;
}

vector<int> getTopK(vector<int> nums, int k){
	if (nums.empty() || k > nums.size() || k <= 0) 
		return{};
	vector<int> ret;
	int begin = 0, end = nums.size() - 1;
	int idx = Partition(nums, begin, end);
	while (idx != k - 1)
	{
		if (idx < k - 1)
		{
			begin = idx + 1;

			idx = Partition(nums, begin, end);
		}
		else
		{
			end = idx - 1;
			idx = Partition(nums, begin, end);
		}
	}

	for (int i = 0; i < k; ++i) 
	{
		ret.push_back(nums[i]);
	}
	return ret;
}

int main()
{
	vector<int> nums{ 1, 2, 3, 4, 6, 9, 8 };
	vector<int> ret = getTopK(nums, 4);
	for (auto &index : ret)
	{
		cout << index << " ";
	}

	cout << endl;
	system("PAUSE");
	return 0;
}

参考博文链接1 参考博文链接2 参考博文链接3

本文由 Ryan 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2019/11/01 12:50