Niuke network: some sorting problems about the k-th number

1. The smallest K Number

Method 1 ： Call directly sort Sort

Well , This line of thought, , Know everything. , Is to call the standard library sort Function to sort directly and then return to the previous k Just a number

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(k==0 || input.size()<k){
            return res;
        }
        sort(input.begin(), input.end());
        return vector<int>(input.begin(), input.begin()+k);
    }
};

Method 2 ： Heap sort

We don't want the smallest k The number? , So it is easy for us to use a large top heap

Ideas as follows ：

For each input The elements in the do the following ：

1. When the heap is not full, it is pressed directly into the heap

2. When the heap arrives k Of size after , If the current element to be processed is smaller than the top of the big top heap , So let's just pop Then press the current element , Otherwise, do nothing , The time complexity of this method is obviously O(nlogn)

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(k==0 || input.size()<k){
            return res;
        }
        priority_queue<int, vector<int>> pq;
        for(int x: input){
            if(pq.size()<k){
                pq.push(x);
            }else{
                if(pq.top() > x){
                    pq.pop();
                    pq.push(x);
                }
            }
        }
        while(!pq.empty()){
            res.push_back(pq.top());
            pq.pop();
        }
        return res;
    }
};

Method 3 ： Quick thinking

It's very clever here , It is the use of the fast platoon partition The returned subscript is used to determine whether the K The smallest number .

partition Here is a core function （ It's the same as in the quick row ）

Thought is ： Take a number as the center , Then use this center to divide the number of an interval into two parts , Part of it is less than , Part of it is larger than this center .

Then there is a call from the upper layer partition Function of , utilize partition The returned subscript determines whether the smallest has been selected K Number ：

1. The subscript is equal to k-1, Explain that it has been completed

2. Subscript p Less than k-1, Explain that it needs to be in the interval [p+1,r] Continue to line up

3. Subscript p Greater than k-1, It means that there are too many , stay [l,p] Line up quickly

Be sure to note that the subscript is used directly here ！！！

class Solution {
public:
    int partition(vector<int> &input, int l, int r){
        int pivot=input[r-1];
        //i The record is better than pivot The position of the big elements 
        //j It is used to find out more than pivot The location of small elements 
        // After walking  i The position is the first greater than... In the right half pivot The subscript position of the element of 
        // So finally we need to exchange pivot And the element at this location 
        int i=l;
        for(int j=i;j<r-1;++j){
            if(input[j]<pivot){
                swap(input[i++], input[j]);
            }
        }
        swap(input[i], input[r-1]);
        return i;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(k==0 || k>input.size()){
            return res;
        }
        int l=0, r=input.size();
        while(l<r){
            int p=partition(input,l,r);
            if(p+1==k){// there p It's a subscript   If p+1 be equal to k   explain 0-k-1 altogether k Number 
                return vector<int>(input.begin(), input.begin()+k);
            }else if(p+1<k){
                l=p+1;
            }else{
                r=p;
            }
        }
        return res;
    }
};

2. Search for the first K Large number

Method 1 ： Quick line up

It is the same idea as the above , The difference is that it is terminated by a number instead of a subscript .

The code is as follows ：

class Solution {
public:
    // Conventional fast platoon Division , But this time the big number is on the left 
    int partion(vector<int>& a, int low, int high){ 
        int temp = a[low];
        while(low < high){
            // Those smaller than the benchmark are on the right 
            while(low < high && a[high] <= temp)
                high--;
            if(low == high)
                break;
            else
                a[low] = a[high];
            // Those larger than the benchmark are on the left 
            while(low < high && a[low] >= temp)
                low++;
            if(low == high)
                break;
            else
                a[high] = a[low];
        }
        a[low] = temp;
        return low;
    }
    int quickSort(vector<int>& a, int low, int high, int K){
        int p = partion(a, low, high); 
        if(K == p - low + 1)  
            return a[p];
        else if(p - low + 1 > K)  
            return quickSort(a, low, p - 1, K);  
        else  
            return quickSort(a, p + 1, high, K - (p - low + 1));  
    }
    int findKth(vector<int> a, int n, int K) {
        return quickSort(a, 0, n - 1, K);
    }
};

Method 2 ： Pile up

The heap method also works well ：

Directly use the big top stack as follows ：

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        priority_queue<int, vector<int>> pq;
        int k=n-K+1;
        for(int x: a){
            if(pq.size()<k){
                pq.push(x);
            }else{
                if(pq.top() > x){
                    pq.pop();
                    pq.push(x);
                }
            }
        }
        return pq.top();
    }
};

In the problem solving section, I saw that the big man wrote the small top pile directly ：

class Solution {
public:
    int *heap;
    int size = 0; //  The number of elements in the initialization heap is 0
    
    int findKth(vector<int> a, int n, int K) {
        heap = new int[K+5];
        for (auto i : a) {
            //  The pile is not full ,  Continue to put elements in the heap 
            if (size < K) {
                add(i);
            } else if (i > top()){
                pop(); 
                add(i);
            }
        }
        
        return top();
    }

    //  Add an element 
    void add(int u) {
        heap[++size] = u;
        up(size); //  Added to the tail ,  Need to adjust up 
    }
    
    //  Heap top element 
    int top() {
        return heap[1];
    }
    
    void pop() {
        heap[1] = heap[size--];
        down(1); // Downward adjustments 
    }
    
    void up(int u) {
        //  Define the current node as cur,  Parent node is f
        int f = u / 2, cur = u;
        //  If there is a parent node and the parent node is larger ,  Explain that it needs to be increased 
        while (f && heap[f] > heap[cur]){
            swap(heap[f], heap[cur]);
            up(f); // f It may also need to be raised ,  recursive 
        }
    }
    
    void down(int u) {
        //  Definition u My left and right sons are lson and rson
        int lson = u << 1, rson = u << 1 | 1;
        
        // t Represents the parent node 、 Left son 、 The subscript of the lowest value in the right son 
        int t = u;
        //  If the left son doesn't cross the line ,  And smaller ,  be t=lson
        if (lson <= size && heap[lson] < heap[t])
            t = lson;
        //  ditto ,  If it is a big pile, change it here 
        if (rson <= size && heap[rson] < heap[t] )
            t = rson;
        //  If u No t, The smallest of the three is a child node , Then exchange with the smallest one 
        if (u != t) {
            swap(heap[u],heap[t]);
            down(t); //  After the change t,  It may be necessary to continue down 
        }
    }
};