【数据结构与算法】寻找无序数组中第K大的数

女爷i 2022-01-20 14:27 224阅读 0赞

### 寻找无序数组中第K大的数 ###

*  方法1：排序法
 *  方法2：插入法
 *  方法3：小顶堆法
 *  方法4：分治法

部分参考：  
[漫画：寻找无序数组的第K大元素][K]  
给定数组如下，求第K大的元素，K=6： ![在这里插入图片描述][2019061422035311.PNG]

# 方法1：排序法 #

先将数组排序，然后按照索引找到第K大的元素  
排序算法见：[常见七种排序算法][Link 1]

# 方法2：插入法 #

1.维护一个长度为k的数组A的有序数组（降序），用于存储已知的k个较大的元素。  
2.遍历原数组，每遍历到一个元素，和数组A中最小的元素相比较，如果小于等于数组A的最小元素，继续遍历；如果大于数组A的最小元素，则插入到数组A中，并把曾经的最小元素删除。  
3.长度为K的数组中，最后一个元素就是第K大的元素  
时间复杂度：O(nk)

# 方法3：小顶堆法 #

1.使用数组的前K个元素，构建一个大小为K的小顶堆  
堆：完全二叉树  
大顶堆：每个结点的值都大于或等于其左右孩子结点的值  
小顶堆：每个结点的值都小于或等于其左右孩子结点的值

2.遍历数组中剩下的元素，和堆顶相比较，如果小于等于堆顶元素，继续遍历；如果大于堆顶元素，则把该元素与堆顶交换，调整堆。  
3.堆顶元素就是第K大的元素。

注意：如果使用小顶堆进行排序，那么得到的序列是降序（因为需要把堆顶元素和未调整部分的最后一个元素交换，那么最小的元素就在最后面）  
从小到大排序：大顶堆  
从大到小排序：小顶堆  
寻找第K大的元素：小顶堆  
寻找第K小的元素：大顶堆

#include <iostream>
    
    using namespace std;
    
    //调整堆
    void adjustHeap(int arr[], int index, int k){
    	int min = index;
    	int left = 2 * index + 1;
    	int right = 2 * index + 2;
    	if (left < k && arr[left] < arr[min]){
    		min = left;
    	}
    	if (right <k && arr[right] < arr[min]){
    		min = right;
    	}
    
    	if (min != index){
    		swap(arr[min], arr[index]);
    		adjustHeap(arr, min, k); //为了使得调整后依旧满足最小堆的特性，需要再次调整
    	}
    }
    
    int findTopK(int arr[], int k,int len){
         //从最后一个叶子节点开始调整堆
    	for (int i = k / 2 - 1; i >= 0; i--){
    		adjustHeap(arr, i, k);
    	}
        
        //遍历剩下的元素
    	for (int i = k; i < len; i++){
    		if (arr[i]>arr[0]){
    			swap(arr[0], arr[i]);
    			adjustHeap(arr, 0, k);
    		}
    	}
    
    	return arr[0];
    }
    
    
    int main()
    {
    	int arr[] = { 7, 5, 15, 3, 17, 2, 20, 24, 1, 9, 12, 8 };
    	int k = 7;
    	int len = sizeof(arr) / sizeof(int);
    
    	int target = findTopK(arr, k,len);
    
    	cout << target<<endl;
    	return 0;
    }

# 方法4：分治法 #

1.利用快速排序的思想，每一次把数组分成较大和较小的两部分，以第一个元素A为基准，把大于A的元素都交换到数组左边，小于A的元素都交换到数组右边。  
2.判断K与A索引的大小，如果K小于A的索引，那么在A的左边再次利用分治法；反之，在A的右侧利用分治法

#include <iostream>
    using namespace std;
    
    //把大的放在左边，小的放在右边
    int partition(int arr[], int i, int j){
    	int temp = arr[i];
    	while (i < j){
    		while (i<j && temp >= arr[j]){
    			j--;
    		}
    		swap(arr[i], arr[j]);
    		while (i<j && temp<=arr[i]){
    			i++;
    		}
    		swap(arr[i], arr[j]);
    	}
    	return  i;
    }
    
    int findMaxK(int arr[], int k, int start, int end){
    	int q = partition(arr, start, end);
    
    	if (q>k){
    		return findMaxK(arr, k, start, q - 1);
    	}
    	else if (q<k){
    		return findMaxK(arr, k, q + 1, end);
    	}
    	
    	return q;
    }
    
    
    int main()
    {
    	int arr[] = { 7, 5, 15, 3, 17, 2, 20, 24, 1, 9, 12, 8 };
    	int k = 6;
    	int len = sizeof(arr) / sizeof(int);
    	
    	int target = findMaxK(arr, k-1,0, len-1);  //第K大的索引是k-1
    	cout << arr[target]<<endl;
    	
    	return 0;
    }

如果用分治法找到第K小的值，那么需要修改partition函数，具体代码如下：

#include <iostream>
    using namespace std;
    
    //把大的放在右边，小的放在左边
    int partition(int arr[], int i, int j){
    	int temp = arr[i];
    	while (i < j){
    		while (i<j && temp <= arr[j]){
    			j--;
    		}
    		swap(arr[i], arr[j]);
    		while (i<j && temp>=arr[i]){
    			i++;
    		}
    		swap(arr[i], arr[j]);
    	}
    	return  i;
    }
    
    int findMinK(int arr[], int k, int start, int end){
    	int q = partition(arr, start, end);
    
    	if (q>k){
    		return findMinK(arr, k, start, q - 1);
    	}
    	else if (q<k){
    		return findMinK(arr, k, q + 1, end);
    	}
    	
    	return q;
    }
    
    
    int main()
    {
    	int arr[] = { 7, 5, 15, 3, 17, 2, 20, 24, 1, 9, 12, 8 };
    	int k = 6;
    	int len = sizeof(arr) / sizeof(int);
    	
    	int target = findMinK(arr, k-1,0, len-1);  //第K小的索引是k-1
    	cout << arr[target]<<endl;
    	
    	return 0;
    }

[K]: https://mp.weixin.qq.com/s/LKrxeFT9S5NEAHlhHI3nSQ
[2019061422035311.PNG]: /images/20220120/6152e1ac0e9e44c8b57221e9e7b0bbac.png
[Link 1]: https://blog.csdn.net/weixin_43930512/article/details/90897648