Question

剑指 Offer II 076. 数组中的第 k 大的数字

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

 

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

 

提示：

• 1 <= k <= nums.length <= 104
• -104 <= nums[i] <= 104

 

注意：本题与主站 215 题相同： https://leetcode.cn/problems/kth-largest-element-in-an-array/

解法

方法一

class Solution:
  def findKthLargest(self, nums: List[int], k: int) -> int:
    def quick_sort(left, right, k):
      if left == right:
        return nums[left]
      i, j = left - 1, right + 1
      x = nums[(left + right) >> 1]
      while i < j:
        while 1:
          i += 1
          if nums[i] >= x:
            break
        while 1:
          j -= 1
          if nums[j] <= x:
            break
        if i < j:
          nums[i], nums[j] = nums[j], nums[i]
      if j < k:
        return quick_sort(j + 1, right, k)
      return quick_sort(left, j, k)

    n = len(nums)
    return quick_sort(0, n - 1, n - k)

class Solution {
  public int findKthLargest(int[] nums, int k) {
    int n = nums.length;
    return quickSort(nums, 0, n - 1, n - k);
  }

  private int quickSort(int[] nums, int left, int right, int k) {
    if (left == right) {
      return nums[left];
    }
    int i = left - 1, j = right + 1;
    int x = nums[(left + right) >>> 1];
    while (i < j) {
      while (nums[++i] < x)
        ;
      while (nums[--j] > x)
        ;
      if (i < j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
      }
    }
    if (j < k) {
      return quickSort(nums, j + 1, right, k);
    }
    return quickSort(nums, left, j, k);
  }
}

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

  int quickSort(vector<int>& nums, int left, int right, int k) {
    if (left == right) return nums[left];
    int i = left - 1, j = right + 1;
    int x = nums[left + right >> 1];
    while (i < j) {
      while (nums[++i] < x)
        ;
      while (nums[--j] > x)
        ;
      if (i < j) swap(nums[i], nums[j]);
    }
    return j < k ? quickSort(nums, j + 1, right, k) : quickSort(nums, left, j, k);
  }
};

func findKthLargest(nums []int, k int) int {
  n := len(nums)
  return quickSort(nums, 0, n-1, n-k)
}

func quickSort(nums []int, left, right, k int) int {
  if left == right {
    return nums[left]
  }
  i, j := left-1, right+1
  x := nums[(left+right)>>1]
  for i < j {
    for {
      i++
      if nums[i] >= x {
        break
      }
    }
    for {
      j--
      if nums[j] <= x {
        break
      }
    }
    if i < j {
      nums[i], nums[j] = nums[j], nums[i]
    }
  }
  if j < k {
    return quickSort(nums, j+1, right, k)
  }
  return quickSort(nums, left, j, k)
}