求第k小元素
题目:
给定线性序集中n个元素和一个整数k,其中1<=k<=n,要求找出这n个元素中第k小的元素。
如果将这n个元素线性序排列时,如果不存在重复的数或者求第k个元素的时候,那么第k个位置即为要找的元素。
当k = 1时,要找的就是最小值;而当k = n时,则要找的则是最大值。
凭借着快速排序中的划分函数,可以实现上面的功能。
对于序列a[p : q],分治算法randomizedSelect会随机选择一个值作为基准值(pivot),在划分之后得到的i,它为基准值所在序列的索引,而基准值把整个序列分成了三部分:分别是小于等于基准值的 a[p: i] 以及基准值 a[ i ] 和大于等于基准值的 a[ i+1 : r ]。
1.求第k个元素
1.1 递归版本
/**
* 模仿快速排序对数组进行递归划分,并对其一子数组递归处理得到第k小元素
* @param nums: 数组
* @param start: 起始索引 基准值
* @param end: 结束索引
* @param k: 第k个元素的索引
* @return: 返回第k个元素的值
*/
template<class Type>
Type randomizedSelect(vector<Type>& nums, int start, int end, int k) {
if (start == end)
return nums[start];
//随机选择一个基准值
int i = randomPartition(nums, start, end);
int rank = i - start + 1;
if (k == rank)
return nums[i];
//左边
else if (k < rank)
return randomizedSelect(nums, start, i - 1, k);
else
return randomizedSelect(nums, i + 1, end, k - rank);
}
注:randomPartition中除了形参由Type nums[]改为了vector<Type> nums外,其余不变。randomizedSelect函数会在每次都丢弃一半的值。
快速排序是对冒泡排序的改进,所以它也有着冒泡排序的特点:每次划分后的基准值就是它的最终位置。在randomizedSelect函数中,为了得到基准值的位置,由start和基准值i的位置得到了当前基准值的排名,即
int rank = i - start + 1;
接着就可以判断k == rank,如果相等的话,那么直接返回该值即可;如果k < rank,则表示第k个值在左半部分,否则则在右半部分。如果在右半部分的话,由于已经知道了 i 的位置为rank,所以在换到右半部分的时候,还应该让k=k-rank。
1.2 非递归版本
由递归形式改为非递归形式,一般会用到循环,有的还会使用到栈。
template<class Type>
Type randomizedSelect(vector<Type>& nums, int start, int end, int k) {
while (start <= end) {
if (start == end)
return nums[start];
//随机选择一个基准值
int i = randomPartition(nums, start, end);
int rank = i - start + 1;
if (k == rank)
return nums[i];
//左边
else if (k < rank) {
end = i - 1;
}
else {
start = i + 1;
k = k - rank;
}
}
return nums[start];
}
代码思路和上面的相同。
2. 求第k小元素
求第k小元素主要考虑的就是重复值的处理。这里给出的解决办法是在每次按照基准值分成三部分的时候,把两侧的与基准值相同的值聚合到一起,这里需要知道相同值的起始索引left和个数count,之后一次遍历知道左半部分总共有多少不重复的值rank。
首先,我们可以根据rank就是left的真实位置,然后可以判断rank == left,如果相等的话,则nums[left]就是第k小元素;如果k < rank,那么k一定散落在左半部分;否则则散落在右半部分。另外,还可以完全去掉基准值和它的相同值们。
其他用到的函数不变,主要改变的就是randomizedSelect函数。
/**
* 模仿快速排序对数组进行递归划分,并对其一子数组递归处理得到第k小元素
* @param nums: 数组
* @param start: 起始索引 基准值
* @param end: 结束索引
* @param k: 第k个元素的索引
* @return: 返回第k个元素的值
*/
template<class Type>
Type randomizedSelect(vector<Type>& nums, int start, int end, int k) {
if (start == end)
return nums[start];
//随机选择一个基准值
int i = randomPartition(nums, start, end);
//聚合与基准值相同的值
int rank = 0;
int count = together(nums, start, end, i, &rank);
if (k == rank)
return nums[i];
//左边
else if (k < rank)
return randomizedSelect(nums, start, i - 1, k);
else
return randomizedSelect(nums, i + 1 + count, end, k - rank);
}
代码结构和之前类似,相对于之前增加了一个聚合相同值函数together()。其余则不变。
/**
* 聚合与基准值相同的值,重新设置基准值为第一个相同值的索引 并返回相同的个数
* @param nums: 数组
* @param start: 起始索引
* @param end: 结束索引
* @param pivot: 基准值索引 可能会被重写
* @param left_rank: 左半部分的真实个数
* @return :返回了与基准值相同的个数 未算上基准值
*/
template<class Type>
int together(vector<Type>& nums, int start, int end, int& pivot, int* left_rank = nullptr) {
//聚合相同值
int left = pivot;
int right = pivot;
//左边相同值聚合
for (int m = start; m < left && left - 1 > start; m++) {
if (nums[m] == nums[pivot]) {
nums[m] = nums[--left];
nums[left] = nums[pivot];
}
}
//右边相同值聚合
for (int m = end; m > right && right + 1 < end; m--) {
if (nums[m] == nums[pivot]) {
nums[m] = nums[++right];
nums[right] = nums[pivot];
}
}
set<Type> unique;
//基准值的真实排名
int rank = 1;
for (int m = start; m < pivot; m++) {
if (nums[m] != nums[pivot] && unique.find(nums[m]) == unique.end()) {
unique.insert(nums[m]);
rank++;
}
}
//重写基准值
pivot = left;
if (left_rank != nullptr)
* left_rank = rank;
return right - left;
}
对于聚合函数together而言,它每次都会遍历nums[start: end]一遍多一点。
前两个循环是为了聚合相同值到一块,第三个循环是为了确定nums[left]的真实排名,这里使用到了c++提供的集合库#include<set>,通过它来确定不重复的值有多少。
接下来则可以简单测试一下:
int main() {
vector<int> a = { 4, 2, 6, 7, 5, 3};
int len = a.size();
int k = 5;
int value = randomizedSelect(a, 0, len - 1, k);
cout << value << endl;
for (int i = 0; i < len; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
另外,本代码通过了牛客网的关于第k小元素的题目。
3.效率
接下来说说效率,在一般情况下,当基准值选的不错的情况下,大约两次次循环能去掉至少一半的值,理论上来说应该要比单纯地使用排序算法然后再遍历要快的。
完整代码:
#include <iostream>
#include <cmath>
#include <random>
#include <set>
using namespace std;
/**
* 对a[p:r]进行划分 扩展两个区域a[p:i]和a[j:r]
* @param nums: 数组
* @param start: 基准值索引 在这里也是第一个值的索引
* @param end: 数组最后一个值的索引
* @return: 基准值所在的索引
*/
template<class Type>
int partition(vector<Type>& nums, int start, int end) {
int left = start, right = end + 1;
Type x = nums[start];
//将 < x的元素交换到左边区域 > x的元素交换到右边区域
while (true) {
while (nums[++left] < x && left < end);
while (nums[--right] > x);
if (left >= right) break;
Type temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
nums[start] = nums[right];
nums[right] = x;
return right;
}
/**
* 随机选择一个基准值index属于[start, end],之后nums[start] 交换 nums[index],
* @params nums: 数组
* @params start: 起始索引
* @params end: 结束索引
* @return: 基准值所在的索引
*/
template<class Type>
int randomPartition(vector<Type>& nums, int start, int end) {
//随机数
default_random_engine random;
int index = random() % (end - start + 1) + start;
//交换值
Type temp = nums[start];
nums[start] = nums[index];
nums[index] = temp;
return partition(nums, start, end);
}
/**
* 聚合与基准值相同的值,重新设置基准值为第一个相同值的索引 并返回相同的个数
* @param nums: 数组
* @param start: 起始索引
* @param end: 结束索引
* @param pivot: 基准值索引 可能会被重写
* @param left_rank: 左半部分的真实个数
* @return :返回了与基准值相同的个数 不包括基准值
*/
template<class Type>
int together(vector<Type>& nums, int start, int end, int& pivot, int* left_rank = nullptr) {
//聚合相同值
int left = pivot;
int right = pivot;
//左边相同值聚合
for (int m = start; m < left && left - 1 > start; m++) {
if (nums[m] == nums[pivot]) {
nums[m] = nums[--left];
nums[left] = nums[pivot];
}
}
set<Type> unique;
//基准值的真实排名
int rank = 1;
for (int m = start; m < pivot; m++) {
if (nums[m] != nums[pivot] && unique.find(nums[m]) == unique.end()) {
unique.insert(nums[m]);
rank++;
}
}
//右边相同值聚合
for (int m = end; m > right && right + 1 < end; m--) {
if (nums[m] == nums[pivot]) {
nums[m] = nums[++right];
nums[right] = nums[pivot];
}
}
//重写基准值
pivot = left;
if (left_rank != nullptr)
* left_rank = rank;
return right - left;
}
/**
* 模仿快速排序对数组进行递归划分,并对其一子数组递归处理得到第k小元素
* @param nums: 数组
* @param start: 起始索引 基准值
* @param end: 结束索引
* @param k: 第k个元素的索引
* @return: 返回第k个元素的值
*/
template<class Type>
Type randomizedSelect(vector<Type>& nums, int start, int end, int k) {
if (start == end)
return nums[start];
//随机选择一个基准值
int i = randomPartition(nums, start, end);
//聚合与基准值相同的值
int rank = 0;
int count = together(nums, start, end, i, &rank);
if (k == rank)
return nums[i];
//左边
else if (k < rank)
return randomizedSelect(nums, start, i - 1, k);
else
return randomizedSelect(nums, i + 1 + count, end, k - rank);
}
int main() {
vector<int> a = { 4, 2, 6, 7, 5, 3};
int len = a.size();
int k = 5;
int value = randomizedSelect(a, 0, len - 1, k);
cout << value << endl;
for (int i = 0; i < len; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}