找数组中的第K小元素

找数组中的第K小元素

题目：在给定数组a中找出第k小的元素。

方法一：模拟小顶堆的排序过程

算法思想：（与小顶堆类似）

1 先设置一个buffer数组，把数组a的前k个元素来初始化数组buffer；

2 然后从数组a的第k+1个元素开始，与buffer数组里最大的元素比较，如果大于buffer数组里最大的元素，则用a[i]的值替换buffer数组里最大的元素；

3 在遍历完数组a之后，数组buffer里最大值即为我们所要求的第k小元素。

完整代码：

#include 
using namespace std;

int findMaxElementIndex(int a[], int n){
	int max = -1, index;
	for(int i = 0; i < n; i++){
		if(a[i] > max){
			max = a[i];
			index = i;
		}
	} 
	return index;
}

int findMaxElement(int a[], int n){
	int max = -1, index;
	for(int i = 0; i < n; i++){
		if(a[i] > max){
			max = a[i];
		}
	} 	
	return max;
}

int findKthMinElement(int a[], int n, int k){
	int buffer[k+1] = {0};//用来存放前k个最小的元素 
	for(int i = 0; i < k; i++){//先初始化buffer数组，把k个元素先填充进buffer 
		buffer[i] = a[i];
	} 
	int index;//用来指向数组buffer中最大的那个元素的下标 
	for(int i = k; i < n; i++){//由于前k个元素已经放入buffer中，所以比较只需要从第k+1个元素开始就行 
		index = findMaxElementIndex(buffer, k);
		if(buffer[index] > a[i]){//小顶堆思想：把数组buffer里最大的元素先换掉 
			buffer[index] = a[i]; 
		}	
	}
	return findMaxElement(buffer, k);//最后buffer数组中最大的元素就是第k小元素 
}

int main(){
	int a[11] = {7, 8, 4, 3, 9, 6, 5, 1, 1, 9};
	int k = 3;//寻找数组a中第三小的元素
	cout << "数组a第" << k << "小的元素= " <<  findKthMinElement(a, 10, k);
	return 0;
}

运行结果:

算法分析： 

时间复杂度：O(n^2), 空间复杂度:O（k)。

方法二：模拟快速排序的过程

算法思想：

完整代码：

#include 
using namespace std;

int findKthMinElement(int a[], int start, int end, int k){//模拟快排过程 
	int i = start, j = end, temp;
	if(start < end){
		temp = a[start];
		while(i != j){
			while(j > i && a[j] >= temp){//如果比基准数大则继续遍历，反之将它放到基准数的左侧 
				j--;
			}
			a[i] = a[j];
			while(j > i && a[i] <= temp){//如果比基准数小则继续遍历，反之将它放到基准数的右侧 
				i++;
			}
			a[j] = a[i]; 
		} 
		a[i] = temp;//将基准数放到它应有的位置上
		if(k-1 == i){
			return a[i];
		}else if(k-1 < i){
			return findKthMinElement(a, start, i-1, k);//在基准数左侧区间的数寻找 
		}else{
			return findKthMinElement(a, i+1, end, k);//在基准数右侧区间的数寻找 
		}		 
	}else if(start == end && start == k-1){//区间里只有一个元素且为a[k-1] 
		return a[k-1];
	}
}

int main(){
	int a[11] = {7, 8, 4, 3, 9, 4, 5, 1, 1, 9};
	int k = 6;//寻找数组a中第三小的元素
	cout << "数组a第" << k << "小的元素= " <<  findKthMinElement(a, 0, 9, k);
	return 0;
}

运行结果：

 

算法分析：设序列a中含有n个元素，其比较次数的递推式为T（n） = T（n/2） + O(n).

 参考资料：LeetCode每日打卡.215.数组中的第K大元素_哔哩哔哩_bilibili

                  chapt3-3-查找-第K小元素_哔哩哔哩_bilibili