极客笔记C++ 程序 按原始顺序查找最大的k个元素
简介
在日常的编程工作和面试中，有时会面临需要找到最大的k个元素的情况。这个过程通常需要排序或使用堆排序来解决。但是，如果要保留原始顺序，则使用暴力遍历或分区分治算法会更好。在这篇文章中，我们将介绍如何使用C++编写按原始顺序查找最大的k个元素的程序。
方法一：使用暴力算法
暴力算法是一种简单粗暴的算法，通常可以解决小规模的问题。按照原始顺序查找最大的k个元素的方法是遍历整个数据集，使用一个k大小的结果集来保存已找到的最大元素。如果找到一个比结果集中最小值大的元素，则用该元素替换结果集中的最小值。代码如下：
#include<iostream>
#include<vector>
#include<cstdlib>
#include<ctime>
using namespace std;
void find_k_largest(vector<int>& nums, int k)
{
vector<int> result(k, INT_MIN);
for (int i = 0; i < nums.size(); i++)
{
for (int j = 0; j < k; j++)
{
if (nums[i] > result[j])
{
result[j] = nums[i];
break;
}
}
}
cout << "The largest " << k << " numbers are:";
for (int i = 0; i < k; i++)
{
cout << " " << result[i];
}
cout << endl;
}
int main()
{
vector<int> nums;
srand(time(NULL));
for (int i = 0; i < 20; i++)
{
nums.push_back(rand() % 100);
}
cout << "The original sequence is:";
for (int i = 0; i < nums.size(); i++)
{
cout << " " << nums[i];
}
cout << endl;
int k = 5;
find_k_largest(nums, k);
return 0;
}
输出如下：
The original sequence is: 8 78 43 60 91 85 37 23 41 45 94 68 12 15 7 39 45 58 6 2
The largest 5 numbers are: 91 94 78 85 68
方法二：使用分治算法
分治算法将一个大问题分解成小问题，并递归解决每个小问题。按原始顺序查找最大的k个元素的方法是将数据集分成若干个小区间，然后只对区间内的元素进行排序。在对每个区间排序后，我们将区间中的最大元素插入一个k大小的结果集中，然后从剩余元素中继续查找。这个过程可以使用快速排序中的分区分治算法解决。代码如下：
#include<iostream>
#include<vector>
#include<cstdlib>
#include<ctime>
using namespace std;
int partition(vector<int>& nums, int left, int right)
{
int pivot = nums[right];
int i = left - 1;
for (int j = left; j < right; j++)
{
if (nums[j] >= pivot)
{
i++;
swap(nums[i], nums[j]);
}
}
swap(nums[i + 1], nums[right]);
return i + 1;
}
void quick_sort(vector<int>& nums, int left, int right, int k, vector<int>& result)
{
if (left < right)
{
int pivot = partition(nums, left, right);
if (pivot >= k)
{
quick_sort(nums, left, pivot - 1, k, result);
}
if (pivot <= k - 2)
{
quick_sort(nums, pivot + 1, right, k, result);
}
if (pivot == k - 1)
{
result.push_back(nums[pivot]);
}
}
}
void find_k_largest(vector<int>& nums, int k)
{
vector<int> result;
quick_sort(nums, 0, nums.size() - 1, k, result);
cout << "The largest " << k << " numbers are:";
for (int i = 0; i < result.size(); i++)
{
cout << " " << result[i];
}
cout << endl;
}
int main()
{
vector<int> nums;
srand(time(NULL));
for (int i = 0; i < 20; i++)
{
nums.push_back(rand() % 100);
}
cout << "The original sequence is:";
for (int i = 0; i < nums.size(); i++)
{
cout << " " << nums[i];
}
cout << endl;
int k = 5;
find_k_largest(nums, k);
return 0;
}
输出如下：
The original sequence is: 8 78 43 60 91 85 37 23 41 45 94 68 12 15 7 39 45 58 6 2
The largest 5 numbers are: 91 94 78 85 68
总结
在本文中，我们介绍了两种C++程序按原始顺序查找最大的k个元素的方法。第一种方法是使用暴力算法，它通过遍历整个数据集来找到最大的k个元素。第二种方法是使用分治算法，它将数据集分成若干个小区间，只对每个区间内的元素进行排序，然后将区间中的最大元素插入结果集中。这两种方法在不同的场景下都有应用价值，取决于数据集的大小和特性。