Leetcode 215. Kth Largest Element in an Array in C [C語言]
==
###### tags: `Leetcode`

## Description
(medium)
Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

You must solve it in O(n) time complexity.

## 思路
因為這題有限制要壓在O(n)，所以可以想到大部分的sorting辦法都是不能用的，想不到有什麼sorting可以用，也試過用O(nlogn)絕對會爆。

這種找第Kth element的問題可以用Quick Select！有點算是quicksort的延伸，最主要的精髓就是partition.

所謂partition就是divide & conquer的分類方式，選一點pivot(我都是選最右，都可以)

可以看看pseudo code

partition(nums, low, high){
    pivot = high
    i = low
    for(j:low->high){
        if(nums[j]>=pivot){
            swap(nums[i], nums[j])
            i++
        }
    }
    swap(i, pivot)
    return i
}


從上面的圖也可以看來他的pivot會有直接切到他在nums中會排到的大小，是一個非常方便的性質。

他的功能就會像是quicksort的步驟一樣，但是這邊我們要修改的是我們不會對pivot左右兩邊都跑遞迴，我們只對所要求的k那一邊一直跑就好了
這樣子速度會快上很多，才可以壓在O(N)

## 程式

void swap(int *a, int *b){
    int tmp=*b;
    *b=*a;
    *a=tmp;
}

int partition(int *arr, int low, int high){
    int pivot = arr[high];
    int i = (low-1);

    for(int j=low; j<high; j++){
        if(arr[j]>=pivot){
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i+1], &arr[high]);
    return i+1;
}

int quickselect(int *nums, int low, int high, int k){
    int pi=partition(nums, 0, high);

    if(pi==k)   return pi;
    else if(pi>k)   quickselect(nums, 0, pi-1, k);
    else    quickselect(nums, pi+1, high, k);
    
    return;
}

int findKthLargest(int* nums, int numsSize, int k){
    return nums[quickselect(nums, 0, numsSize-1, k-1)];
}

**Runtime: 141 ms**
runtime beats 78.14 % of c submissions.
**Memory Usage: 11.4 MB**
memory usage beats 74.19 % of c submissions.