{%hackmd @lumynou5/dark-theme %}
# leetcode 215 Kth Largest Element in Array
[原題](https://leetcode.com/problems/kth-largest-element-in-an-array/description/) 要找出未排序數組中 第K大的元素
**[先推一下這篇 排序跟搜索都講很細](https://web.ntnu.edu.tw/~algo/Sort.html)**

### 1.排序
簡單來說就是懶
#### qsort版 直接排序大到小

int cmp(const void*a,const void*b){return *(int*)b-*(int*)a;}
int findKthLargest(int*a,int n,int k){
    qsort(a,n,4,cmp);//126ms,13.2mb
    return a[k-1];
}

時間複雜度平均$O(nlogn)$最差$O(n^2)$ 空間$O(1)$
還能不能更快呢
#### std::sort(introsort)版

int findKthLargest(vector<int>&v,int k){
    //sort(v.rbegin(),v.rend());//168ms,45.3mb
    sort(v.begin(),v.end(),greater<>());//114ms,45.5mb
    //兩種都行
    return v[k-1];
}

時間複雜度平均$O(nlogn)$最差$O(nlogn)$ 空間$O(1)$
解決了worse case
但是還能快

### 2.QuickSelect
用跟quick sort一樣的想法去做 但是不用把排序排完
一樣可以用STL

int findKthLargest(vector<int>&v,int k){
    nth_element(v.begin(),v.begin()+k-1,v.end(),greater<>());//91ms,45.6mb
    return v[k-1];
}

時間複雜度平均$O(n)$最差$O(n^2)$ 空間$O(1)$
也可以跟quick sort變intro sort一樣 讓quick select變intro select
時間複雜度平均$O(n)$最差$O(n)$ 空間$O(1)$
### 3.priority_queue
#### STL pq
用pq好寫的方法當然是全部push進去再pop k次

int findKthLargest(vector<int>&v,int k){
    priority_queue<int> pq;
    for(int e:v)pq.push(e);
    for(;--k;)pq.pop();
    return pq.top();
}
//130ms,49.9mb

時間複雜度平均$O(nlogn)$最差$O(n^2)$(數列遞減時) 空間$O(n)$
既然速度跟qsort一樣慢 空間花最多
而且會pq的人還比會std::sort的人少 那為甚麼我還要提呢
#### linear pq
**[SA 流 C++ 競程修練心法](https://hackmd.io/@sa072686/cp/%2FGTdCSUuiR56t0K7TxtlF7A)**
~~雖然我不是中一中的同學但是~~我在網路上剛好找到
正常的pq是逐次push進去 然後逐次shift down($O(logn)$) 所以要$O(nlogn)$
但是先把n個值全部放進去 再開始做shift down 每做完一次就有一個值的位置固定下來
所以做到後面要動的值會越來越少 複雜度是$O(n)$ 連結原文有詳細證明
(注意 這個數組下標要從1開始 因為我們假設$i$是根節點 $2i-1$是左節點 $2i$是右節點)

void shift_down(vector<int>&v,int n,int now){
    int next;
    while(now<<1<=n){//當左節點還在heap內
        next=now<<1;//先預設下個是左邊
        if(now<<1|1<=n&&v[now<<1|1]>v[now<<1])next|=1;
        //如果有右節點 而且右節點大 就把下一格設成右邊
        if(v[now]>=v[next])break;//根節點大 不用繼續推
        v[now]^=v[next]^=v[now]^=v[next];//往下交換
        now=next;//下一個循環
    }
}
void pop(vector<int>&v){
    v[1]=v[v.size()-1];//刪掉第1項 把最後一項拿過來
    v.erase(v.begin()+v.size()-1);//刪掉最後一項
    shift_down(v,v.size()-1,1);//重新排好
}
int findKthLargest(vector<int>&v,int k){
    v.insert(v.begin(),0);//需要下標從1開始 隨便插個數 不過這個動作也要O(n)
    for(int n=v.size()-1,i=n;i;--i)shift_down(v,n,i);//這段只要O(n)
    for(;--k;)pop(v);//跟建heap的時候一樣 數量會越來越少 最差一樣是O(n)
    return v[1];
}
//171ms,45.4mb

時間複雜度平均$O(n)$最差$O(n)$ 空間$O(1)$
常數偏大 尤其vector第一個insert跟每次的erase
可以開個a[n+1]降常數
#### linear pq但是陣列降常數

void shift_down(int*a,int n,int now){
    int next;
    while(now<<1<n){//當左節點還在heap內
        next=now<<1;//先預設下個是左邊
        if(now<<1|1<n&&a[now<<1|1]>a[now<<1])next|=1;
        //如果有右節點 而且右節點大 就把下一格設成右邊
        if(a[now]>=a[next])break;//根節點大 不用繼續推
        a[now]^=a[next]^=a[now]^=a[next];//往下交換
        now=next;//下一個循環
    }
}
void pop(int*a,int&n){
    a[1]=a[--n];//刪掉第1項 把最後一項拿過來 順便刪掉最後一項(不用真刪)
    shift_down(a,n,1);//重新排好
}
int findKthLargest(vector<int>&v,int k){
    int n=v.size()+1,i=n,a[100005]={0};
    for(;--i;)a[i]=v[i-1];//需要下標從1開始 還是要O(n)
    for(i=n;--i;)shift_down(a,n,i);//這段只要O(n)
    for(;--k;)pop(a,n);///跟建heap的時候一樣 數量會越來越少 最差一樣是O(n)
    return a[1];
}
//130ms,45.8mb

時間複雜度不變 空間$O(n)$
可惜常數還是有點大 最後還是比quick select跟兩個排序慢 甚至跟STL pq差不多
不過可能是測資不夠強
但是是一個很炫的作法 用了兩次的均攤 最後居然可以最差O(n)