current position:Home>Leetcode215 - the kth largest element in the array - quick sort - quick select - template

Leetcode215 - the kth largest element in the array - quick sort - quick select - template

2022-04-29 09:48:30Li Fan, hurry up

Original link
 Insert picture description here

Note: I still have to memorize the template of snapshot

Make some improvements on the basis of fast platoon , Come on, after each split in half , See which side you're looking for , Just go further to which side

Note that the question is K Big element , Let's sort the array from large to small , that nums[k - 1] That's the result ( In the question K It's from 1 At the beginning )

The code is as follows :

class Solution {
    
public:
    int qs(vector<int>& nums, int l, int r, int k){
    
        if(l == r)  return nums[k];
        int x = nums[l], i = l - 1, j = r + 1;
        while(i < j){
    
            do i ++; while(x < nums[i]);
            do j --; while(x > nums[j]);
            if(i < j)   swap(nums[i], nums[j]);
        }
        if(k <= j) return qs(nums, l, j, k);
        else    return qs(nums, j + 1, r, k);
    }

    int findKthLargest(vector<int>& nums, int k) {
    
        return qs(nums, 0, nums.size() - 1, k - 1);
    }
};

copyright notice
author[Li Fan, hurry up],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2022/119/202204290710052397.html

Random recommended