数组中选出前K大的数(top K)

/ C++ / 2 条评论 / 510浏览

数组中选出前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