Topk algorithm_topn algorithm

Hello everyone, meet again, I am your friend Quanzhanjun.

topK algorithm

Idea 1: Quick Selection Algorithm The fast selection algorithm can be used. With the help of quick sorting, let mid be the intermediate result of each division. After each division, if mid==k, it means that the sequence is just right, and the k th position and the position in front of him are the largest in the top K number, if mid < k, it means that the K-th largest element is in the second half, then the first half must be the largest number in the top K, just find K from the second half-mid large number, otherwise if mid > k, It means that the K-th largest number is in the first half, just find the first K-large number from the first half. Time complexity: Assuming that the mids of each division are in the middle, each layer is only divided into half, so the amount of data for each division is n,n/2,n/4,n/8...There are a total of logn layers. According to the proportional sequence, the time complexity can be calculated as O(n) C++ code demo

#include<bits/stdc++.h>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 2e5 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9;
int partion(int l,int r,int a[]){ 
   
    int x = a[l];
    while(l < r){ 
   
        while(l < r && a[r] < x)r --;
        if(l < r)a[l ++] = a[r];
        while(l < r && a[l] > x)l ++;
        if(l < r)a[r --] = a[l];
    }
    a[l] = x;
    return l;
}
int quickSort(int l,int r,int a[],int k){ 
   
    if(l < r){ 
   
        int mid = partion(l,r,a);		//Division result
        int ls = mid - l + 1;   //How many numbers are there in [l,mid]
        if(ls == k)return;      //If the divided mid happens to be the K th largest number
        if(ls < k)quickSort(mid + 1,r,a,k - ls);   //If the K th largest number is in the second half
        else quickSort(l,mid - 1,a,k);  //If the K th largest number is in the first half
    }
}
int main(){ 
   
    int a[] = { 
   3,2,3,1,2,4,5,5,6};
    int k = 4;
    quickSort(0,8,a,k);
    for(int i = 0;i < k;i ++)
        cout<<a[i]<<" ";
    return 0;
}
copy

Idea 2: Heap Sort A small top heap of size K can be established. Each time the current number is compared with the top of the small top heap. If the current number is large, the top of the heap is replaced and the heap is readjusted. Time complexity: Adjusting the heap is O(logK), so the total time complexity is nlog(K)

C++ code

#include<bits/stdc++.h>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 2e5 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9;
priority_queue<int,vector<int>,greater<int> >pq;  //The default is the big top heap
int main(){ 
   
    int k = 3;
    int a[] = { 
   3,1,5,2,4,3};
    for(int i = 0;i < 3;i ++)pq.push(a[i]);
    for(int i = 3;i < 6;i ++){ 
   
        if(pq.top() < a[i]){ 
   
            pq.pop();
            pq.push(a[i]);
        }
    }
    while(!pq.empty()){ 
   
        cout<<pq.top()<<endl;
        pq.pop();
    }
    return 0;
}
copy

Compared The heap scheme only needs to open up K array spaces, and does not need to change the original array, while the random selection needs to change the original array, if not, it needs to create an O(n) array

leetcode example Original title link K th largest element in an array Find the k th largest element in an unsorted array. Note that you need to find the k-th largest element of the sorted array, not the k-th distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2 Output: 5 Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4 illustrate:

You can assume that k is always valid and 1 ≤ k ≤ the length of the array.

answer 1. Quick select version

class Solution { 
   
public:
    int partion(int l,int r,vector<int>&nums){ 
   
        int x = nums[l];
        while(l < r){ 
   
            while(l < r && nums[r] < x)r --;
            if(l < r)nums[l ++] = nums[r];
            while(l < r && nums[l] > x)l ++;
            if(l < r)nums[r --] = nums[l];
        }
        nums[l] = x;
        return l;
    }
    void quickSort(int l,int r,vector<int>&nums,int k){ 
   
        if(l < r){ 
   
            int mid = partion(l,r,nums);
            int lnum = mid - l + 1;     //How many numbers are there in [l,mid]
            if(k == lnum)return;
            if(k < lnum)quickSort(l,mid - 1,nums,k);
            else quickSort(mid + 1,r,nums,(k - lnum));
        }
    }
    int findKthLargest(vector<int>& nums, int k) { 
   
        quickSort(0,nums.size() - 1,nums,k);
        return nums[k - 1];
    }
};
copy

2. Priority queue version

class Solution { 
   
public:
    int findKthLargest(vector<int>& nums, int k) { 
   
        priority_queue<int,vector<int>,greater<int> >pq;
        for(int i = 0;i < k;i ++)pq.push(nums[i]);
        for(int i = k;i < nums.size();i ++){ 
   
            if(pq.top() < nums[i]){ 
   
                pq.pop();
                pq.push(nums[i]);
            }
        }
        return pq.top();
    }
};
copy

Tags: C++

Posted by madhu on Wed, 21 Sep 2022 21:47:35 +0300