简单归并排序

问题：

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,Given [3,2,1,5,6,4] and k = 2, return 5.

Note: You may assume k is always valid, 1 ≤ k ≤ array's length.

将数组内的元素排序后直接得出，考虑用归并排序。

答案：

class Solution {public:    int findKthLargest(vector<int>& nums, int k) {        int size = nums.size();        merge_sort(nums, 0, size - 1);        return nums[size - k];    }PRivate:    void merge(vector<int> &nums, int p, int q, int r) {        vector<int> L1;        for(int i = p; i < q + 1; i++) {        L1.push_back(nums[i]);}        vector<int> L2;        for(int i = q + 1; i < r + 1; i++) {        L2.push_back(nums[i]);}        L1.push_back(INT_MAX);        L2.push_back(INT_MAX);        int i = 0, j = 0;        for(int k = p; k < r + 1; k++) {            if(L1[i] < L2[j]) {                nums[k] = L1[i];                i++;            }            else {                nums[k] = L2[j];                j++;            }        }     }    void merge_sort(vector<int> &nums, int p, int r) {        if(p < r) {            int q = (p + r) / 2;            merge_sort(nums, p, q);            merge_sort(nums, q + 1, r);            merge(nums, p, q, r);        }    }};