欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求第k小元素

程序员文章站 2024-03-02 23:05:22
...

题目:

给定线性序集中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个值在左半部分,否则则在右半部分。如果在右半部分的话,由于已经知道了 的位置为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;
}

 

相关标签: 第k小元素