Kth Largest Element

Question:
http://www.lintcode.com/en/problem/kth-largest-element/
Find K-th largest element in an array.
You can swap elements in the array.

Answer:

class Solution {
public:
    /*
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    inline void qsort(vector<int> &nums, int left, int right) {
        if (left >= right)
            return;
        int mid = nums[(left + right)/2];
        int l = left;
        int r = right;
        while (l < r) {
            while(nums[l] < mid) ++l;
            while(nums[r] > mid) --r;
            if (l >= r) break;
            nums[l] = nums[l] + nums[r];
            nums[r] = nums[l] - nums[r];
            nums[l] = nums[l] - nums[r];
            ++l;
            --r;
        }
        if (l == r) l++;
        if (left < r) qsort(nums, left, l - 1);
        if (l > left) qsort(nums, r + 1, right);
    }
    int kthLargestElement(int n, vector<int> &nums) {
        // write your code here
        qsort(nums, 0, nums.size() - 1);
        return nums[nums.size() - n];
    }
};

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️