数组中的第K个最大元素

LIZHAO • • LeetCode
阅读量 0 次 • 评论量 0 个

题目：数组中的第K个最大元素

掌握程度：★ ★ ☆

先了解快速排序

快速排序 挖坑填数 分治法。

  1. 选定一个基准值（随机选着），用tmp保存.
  2. 使用low、high 两个标志，分别指向数组开始和数组结尾。
  3. 先从左向右扫描，扫描到比基准值小的值时停下，并将high的值赋值给low。
  4. 然后从右向左扫描，扫描到比基准值大的值时停下，并将low的值赋值给high。
  5. 然后依次递归左侧数组和右侧数组。

int partition(std::vector<int> &array, int left, int right) {
    int base = array[left];
    while (left < right) {
        while (left < right && array[right] >= base) {
            right--;
        }
        array[left] = array[right];
        while (left < right && array[left] <= base) {
            left++;
        }
        array[right] = array[left];
    }
    array[left] = base;
    return left;
}


void quickSort(std::vector<int> &array, int left, int right) {
    if (left < right) {
        int idx = partition(array, left, right);
        quickSort(array, left, idx - 1);
        quickSort(array, idx + 1, right);
    }
}

数组中的第K个最大元素

借助上面的快速排序的思想，快速排序会将数组分为两部分，左侧部分比基准值小，右侧部分比基准值大。

用数组的元素的个数减去k，得到得到第K个元素在数组中的下标，通过与分区得到的下标比较，最终得到第K大的元素。

class Solution {
public:
    int findKthLargest(vector<int> &nums, int k) {
        int l = 0, r = nums.size() - 1;
        int n = nums.size();
        while (l < r) {
            int p = partition(nums, l, r);
            if (p == n - k) {
                return nums[n - k];
            } else if (p < n - k) {
                l = p + 1;
            } else if (p > n - k) {
                r = p;
            }
        }
        return nums[n - k];
    }
    int partition(std::vector<int> &array, int left, int right) {
        int base = array[left];
        while (left < right) {
            while (left < right && array[right] >= base) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= base) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = base;
        return left;
    }
};
喵~