寻找第k个最大数

绝地灬酷狼 2023-06-19 09:45 13阅读 0赞

在未排序的数组中找到第 **k** 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

**示例 1:**

输入: [3,2,1,5,6,4] 和 k = 2
    输出: 5

**示例 2:**

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
    输出: 4

**说明:**

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

使用分治法解决，和快速排序升序的思想接近。

设置双指针，low和high，找个基准值，使其和low中的值交换  
开始从下标为left = low+1开始走，要是数组中left小于high，并且left为下标的值大于等于bound，则left继续左移，否则移动high，要是以high为下标中的值小于基准值，则右移，否则要是当前left<high，则交换Left和high中的值，并使high在左移一个单位，left右移一个单位，要是left大于right，就跳出，否则继续上述比较！

跳出循环，交换最后right和low为下标的数组元素的值。  
并返回此前right的值。right右边的都是比基准值大的，左边的都是比基准值小的。  
right为当前基准值的下标  
判断当前基准值的下标和指定的元素位次，要是比位次大，使high=right-1  
要是相等的话，就返回right  
要是位次小于right的话，使low=right+1

具体实现源代码：

#include <iostream>
    #include <vector>
    using namespace std ;
    
    class Solution {
        
    public:
        int findKthLargest(vector<int>& nums, int k) {
        
            vector<int> ls(nums.size()) ;
            int low = 0 ;
            int high = nums.size()-1 ;    
            int mid = 0 ;
            while(low <= high) {
        
                mid = partition(low, high, nums) ;
                if(mid == k-1) {
        
                    return nums[mid] ;
                }
                if(mid < k-1) {
        
                    low = mid+1 ;
                }
                if(mid > k-1) {
        
                    high = mid-1 ;
                }
            }
            return -1 ;
        }
    
        int partition(int low , int high, vector<int>&nums) {
        
            int left = low+1;
            int right = high ;
            swap(nums[low], nums[(high+low)/2]) ;
            int bound = nums[low] ;
            while(left <= right) {
        
                while(left < high && nums[left] >= bound) left++ ;
                while(nums[right] < bound) right-- ;
                if(left < right) {
        
                    swap(nums[right--], nums[left++]) ;
                }
                else break ;
            }
            swap(nums[low], nums[right]) ;
            return right ;
        }
    
        void swap(int& l1, int& l2) {
        
            int tmp = l1 ;
            l1 = l2 ;
            l2 = tmp ;
        }
    };
    
    int main() {
        
        vector<int> ls ;
        while(1) {
        
            int a ;
            cin >> a ;
            if(a == -1) break ;
            ls.push_back(a) ;
        }
        Solution ss ;
        int num ;
        cin >> num ;
        cout << ss.findKthLargest(ls, num) << endl ;
        return 0;
    }