Kth Largest Element

Find K-th largest element in an array.

http://www.lintcode.com/en/problem/kth-largest-element/

Discussion

quick sort 实现O(n) run time.

在快速排序算法基础上修改。

https://github.com/kamyu104/LintCode/blob/master/C%2B%2B/kth-largest-element.cpp

为什么这个算法是O(n)复杂度？

Just like with binary search, we keep dropping a segment from the array as we are getting closer to the solution. On average, we halve the search space so it gives us a geometrical series of operations. In the first step, we work with all the items, which is N. The next iteration works only with roughly the half of the array, which is N/2 and so on:
Work = n + n/2 + n/4 + …

Solution quick selection algorithm

// Time:  O(n * logk)
// Space: O(1)
class Solution {
public:
    /*
     * param k : description of k
     * param nums : description of array and index 0 ~ n-1
     * return: description of return
     */
    int kthLargestElement(int k, vector<int> A) {
        // write your code here
        int end = A.size()-1;
        int start = 0;
        //k = A.size() - k + 1;
        while (start + 1 < end) {
            int mid = partition2(A, start, end);
            if (mid == k - 1) {
                return A[mid];
            }
            else if (mid > k - 1) {
                end = mid - 1;//mid已经是pivot的index了，所以要移动1
            }
            else {
                start = mid + 1;
            }
        }
        if (start == k - 1) return A[start];
        return A[end];
    }

    int partition(vector<int> &nums, int start, int end) {
        int pivot = nums[end];
        int i = start;//nums[0~i] >= pivot, i is the current postion for >=pivot
        for(int j = start; j<end; j++) {
            if(nums[j] >= pivot) {
                swap(nums[i], nums[j]);
                i++;
            }
        }
        swap(nums[end], nums[i]);
        return i;
    }

Folow up

如果nums是有序的，采用排序算法时间复杂度会提升到O(n^2)，一个解决办法是randomly generate the pivot

int partition(vector<int> &nums, int start, int end) {
        srand(time(NULL));
        int idx = rand()%(end-start+1) + start;//generate a random index for pivot
        int pivot = nums[idx];
        swap(nums[end], nums[idx]);
        int i = start;//nums[0~i] <= pivot， i is the current postion where nums[i] <= pivot
        for(int j = start; j<end; j++) {
            if(nums[j] <= pivot) {
                swap(nums[i], nums[j]);
                i++;
            }
        }
        swap(nums[i], nums[end]);
        return i;
    }

Follow up again

考虑到数组小的时候不用quick sort用insertion sort。

class Solution {
public:
    /*
     * param k : description of k
     * param nums : description of array and index 0 ~ n-1
     * return: description of return
     */
    int kthLargestElement(int k, vector<int> nums) {
        int start = 0;
        int end = nums.size()-1;
        const int INSERTION_CUTOFF = 15;
        while(start <= end) {
            if(start + INSERTION_CUTOFF > end) {
                InsertionSort(nums, start, end);
                return nums[k-1];
            }
            int p_id = partition(nums, start, end);
            if(p_id == k-1) {
                return nums[p_id];
            } else if(p_id > k-1) {
                end = p_id - 1;
            } else {
                start = p_id +1;
            }
        }
    }
    int partition(vector<int> &nums, int start, int end) {
        int random_id = start + rand()%(end-start+1);
        swap(nums[random_id], nums[end]);
        int pivot = nums[end];
        int i = start;
        for(int j = start; j<end; j++) {
            if(nums[j] >= pivot) {
                swap(nums[i++], nums[j]);
            }
        }
        swap(nums[end], nums[i]);
        return i;
    }
    void InsertionSort(vector<int> &nums, int start, int end) {
        for(int j = start+1; j<=end; j++) {
            int key = nums[j];
            int i = j-1;//find the right postion from start~j-1
            while(i>=start && nums[i]<key) {
                nums[i+1] = nums[i];
                i--;
            }//after this inner loop, i is start-1 or nums[i]>=key, so i+1 is the right place for key
            nums[i+1] = key;
        }
    }
};

你以为这就完了，NO....

Solution 2 max-heap

用priority_queue，堆排序，默认的刚好就是最大堆。建大小为N的堆，弹出的第K个值就是第K大的。时间复杂度：O(N) + O(KlogN)

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.size() < k) return 0;
        priority_queue<int> myheap(nums.begin(), nums.end());
        while(k>1) {
            myheap.pop();
            k--;
        }
        return myheap.top();
    }
};

Solution 3 min-heap

建大小为K的最小堆，用剩余N-K个输入维护最小堆，若新来元素比堆顶元素大，则弹出，插入新元素。这样这个最小堆存储的就是前K大的数，堆顶就是第K大。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.size() < k) return 0;
        priority_queue<int, vector<int>, greater<int>> myheap(nums.begin(), nums.begin()+k);
        for(auto it = nums.begin()+k; it != nums.end(); it++) {
            if(*it > myheap.top()) {
                myheap.pop();
                myheap.emplace(*it);
            }
        }
        return myheap.top();
    }
};

Solution 4 自定义max-heap

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.size() < k) return 0;
        BuildMaxHeap(nums, 0, nums.size()-1);
        //output top K
        int n = nums.size()-1;
        for(int i=0; i<k-1; i++) {//pop k-1 times
            swap(nums[0], nums[n--]);
            maxHeapify(nums, 0, n);
        }
        return nums[0]; //kth largest
    }
    void maxHeapify(vector<int>& nums, int i, int right) {
        int max_id = i;
        int l_id = 2*i +1;
        int r_id = 2*i +2;
        //find the largest from i, l, r
        if(l_id <= right && nums[l_id] > nums[max_id]) {
            max_id = l_id;
        }
        if(r_id <= right && nums[r_id] > nums[max_id]) {
            max_id = r_id;
        }
        //if max_id is not i, swap nums[i] and nums[max_id]
        if(max_id != i) {
            swap(nums[i], nums[max_id]);
            //continue to heapify from the new max_id
            maxHeapify(nums, max_id, right);
        }
    }
    void BuildMaxHeap(vector<int> &nums, int start, int end) {
        for(int i = (end-start-1)/2; i>=start; i--) {//heapify non-leaf nodes
            maxHeapify(nums, i, end);
        }
    }
};

implement a max heap, use it

class MyMaxHeap {
public:
    MyMaxHeap() {};
    void MaxHeap(vector<int> &a, int i, int right) {
        int max_index = i;
        int l_index = i * 2 + 1;//left node
        int r_index = i * 2 + 2;//right node
        //find which one is the largest
        if (l_index <= right && a[l_index] > a[max_index]) {
            max_index = l_index;
        }
        if (r_index <= right && a[r_index] > a[max_index]) {
            max_index = r_index;
        }
        //if max_index is NOT i, swap it
        //如果a[i]是最大的，则以i为根的子树已是最大堆, 否则i的子节点有最大元素  
        //则交换a[i],a[max_index],从而使i及子女满足堆性质 
        if (max_index != i) {
            swap(a[i], a[max_index]);
            //adjust heap 重新调整以max_index为根的子树
            MaxHeap(a, max_index, right);
        }

    }
    //convert a to a max_heap
    void BuildMaxHeap(vector<int> &a) {
        for (int i = 0; i<a.size(); i++) {
            Insert(a[i]);
        }
    }


    int top() {
        return heap[0]; //max
    }
    void pop() {
        swap(heap[0], heap[heap.size() - 1]);
        heap.pop_back();
        MaxHeap(heap, 0, heap.size()-1);
    }

    void Insert(int val) {
        heap.emplace_back(val);
        int i = heap.size() - 1; //the postion of the new value
        //bottom-up heapify it
        while (i>0 && heap[i] > heap[(i - 1) / 2]) {
            swap(heap[i], heap[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    }
    vector<int> heap;
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.size() < k) return 0;
        MyMaxHeap heap;
        heap.BuildMaxHeap(nums);
        //output top K
        int n = nums.size()-1;
        for(int i=0; i<k-1; i++) {//pop k-1 times
            heap.pop();
        }
        return heap.top(); //kth largest
    }
};

Solution 5 自定义 min-heap

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.size() < k) return 0;
        BuildMinHeap(nums, 0, k-1);
        //maintain
        int n = nums.size();
        for(int i=k; i<n; i++) {//
            if(nums[i] > nums[0]) {
                swap(nums[0], nums[i]);
                minHeapify(nums, 0, k-1);
            }
        }
        return nums[0]; //kth largest
    }
    void minHeapify(vector<int>& nums, int i, int right) {
        int min_id = i;
        int l_id = 2*i +1;
        int r_id = 2*i +2;
        //find the largest from i, l, r
        if(l_id <= right && nums[l_id] < nums[min_id]) {
            min_id = l_id;
        }
        if(r_id <= right && nums[r_id] < nums[min_id]) {
            min_id = r_id;
        }
        //if max_id is not i, swap nums[i] and nums[min_id]
        if(min_id != i) {
            swap(nums[i], nums[min_id]);
            //continue to heapify from the new min_id
            minHeapify(nums, min_id, right);
        }
    }
    void BuildMinHeap(vector<int> &nums, int start, int end) {
        for(int i = (end-start-1)/2; i>=start; i--) {//heapify non-leaf nodes
            minHeapify(nums, i, end);
        }
    }
};

Implement a min heap, use it

class MyMinHeap {
public:
    MyMinHeap() {};
    void MinHeap(vector<int> &a, int i, int right) {
        int max_index = i;
        int l_index = i * 2 + 1;//left node
        int r_index = i * 2 + 2;//right node
        //find which one is the largest
        if (l_index <= right && a[l_index] < a[max_index]) {
            max_index = l_index;
        }
        if (r_index <= right && a[r_index] < a[max_index]) {
            max_index = r_index;
        }
        //if max_index is NOT i, swap it
        //如果a[i]是最大的，则以i为根的子树已是最大堆, 否则i的子节点有最大元素  
        //则交换a[i],a[max_index],从而使i及子女满足堆性质 
        if (max_index != i) {
            swap(a[i], a[max_index]);
            //adjust heap 重新调整以max_index为根的子树
            MinHeap(a, max_index, right);
        }

    }
    //convert a to a max_heap
    void BuildMinHeap(vector<int> &a) {
        for (int i = 0; i<a.size(); i++) {
            Insert(a[i]);
        }
    }


    int top() {
        return heap[0]; //max
    }
    void pop() {
        swap(heap[0], heap[heap.size() - 1]);
        heap.pop_back();
        MinHeap(heap, 0, heap.size()-1);
    }

    void Insert(int val) {
        heap.emplace_back(val);
        int i = heap.size() - 1; //the postion of the new value
        //bottom-up heapify it
        while (i>0 && heap[i] < heap[(i - 1) / 2]) {
            swap(heap[i], heap[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    }
    vector<int> heap;
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.size() < k) return 0;
        MyMinHeap heap;
        for(int i = 0; i<k; i++) {
            heap.Insert(nums[i]);
        }
        //maintain
        int n = nums.size();
        for(int i=k; i<n; i++) {//
            if(nums[i] > heap.top()) {
                heap.pop();
                heap.Insert(nums[i]);
            }
        }
        return heap.top(); //kth largest
    }
};