LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 这就是 std::nth_element 的功能，使用快速排序划分的思想，目标只在一边，只需要单边查找，时间复杂度 O(n)

class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    int t = size(nums) - k;  // 第 k 个最大元素即第 n - k + 1 个最小元素
    nth_element(begin(nums), begin(nums) + t, end(nums));
    return nums[t];
  }
};

• 也可以直接用降序划分

class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    nth_element(begin(nums), begin(nums) + k - 1, end(nums), greater<int>{});
    return nums[k - 1];
  }
};

• 升序划分解法

class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    return nth(nums, 0, size(nums) - 1, size(nums) - k);
  }

  int nth(vector<int>& nums, int l, int r, int k) {
    int n = partition(nums, l, r);
    if (n == k) {
      return nums[n];
    }
    return n > k ? nth(nums, l, n - 1, k) : nth(nums, n + 1, r, k);
  }

  int partition(vector<int>& nums, int l, int r) {
    int i = l;
    int j = r;
    while (i < j) {                          // 注意不要误写成 l < r
      while (i < j && nums[j] >= nums[l]) {  // 必须先从右侧开始
        --j;
      }
      while (i < j && nums[i] <= nums[l]) {
        ++i;
      }
      if (i < j) {  // 必须有判断条件
        swap(nums[i], nums[j]);
      }
    }  // i == j，nums[i] 为最后一个比基数小的数，i 即为划分点
    swap(nums[i], nums[l]);
    return i;
  }
};

• 把基数换成右边界即可降序划分

class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    return nth(nums, 0, size(nums) - 1, k - 1);
  }

  int nth(vector<int>& nums, int l, int r, int k) {
    int n = partition(nums, l, r);
    if (n == k) {
      return nums[n];
    }
    return n > k ? nth(nums, l, n - 1, k) : nth(nums, n + 1, r, k);
  }

  int partition(vector<int>& nums, int l, int r) {
    int i = l;
    int j = r;
    while (i < j) {  // 以 nums[r] 为基数，比基数大的放左侧，比基数小的放右侧
      while (i < j && nums[i] >= nums[r]) {  // 此时必须从左侧开始查找
        ++i;
      }
      while (i < j && nums[j] <= nums[r]) {
        --j;
      }
      if (i < j) {
        swap(nums[i], nums[j]);
      }
    }
    swap(nums[i], nums[r]);
    return i;
  }
};