数组中的第K个最大元素

核心：快速排序，扩展只排多少个。

java

public int findKthLargest(int[] nums, int k) {
    if (nums.length < 1 || k < 1 || k > nums.length) {
        return -1;
    }
    return partition(nums, 0, nums.length - 1, nums.length - k);
}

public int partition(int[] nums, int start, int end, int k) {
    if (start >= end) {
        return nums[k];
    }
    int left = start;
    int right = end;
    int pivot = nums[(right - start) / 2 + start];
    while (left <= right) {
        while (left <= right && nums[left] < pivot) {
            left++;
        }
        while (left <= right && nums[right] > pivot) {
            right--;
        }
        if (left <= right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
    if (k >= left) {
        return partition(nums, left, end, k);
    }
    if (k <= right) {
        return partition(nums, start, right, k);
    }
    return nums[k];
}

go

func findKthLargest(nums []int, k int) int {
   if len(nums) < 1 || k < 1 || k > len(nums) {
      return -1
   }
   return partition(nums, 0, len(nums)-1, len(nums)-k)
}
func partition(nums []int, start, end, k int) int {
   if start >= end {
      return nums[k]
   }
   pivot := nums[(end-start)/2+start]
   left, right := start, end
   for left <= right {
      for left <= right && nums[left] < pivot {
         left++
      }
      for left <= right && nums[right] > pivot {
         right--
      }
      if left <= right {
         nums[left], nums[right] = nums[right], nums[left]
         left++
         right--
      }
   }
   if k >= left {
      return partition(nums, left, end, k)
   }
   if k <= right {
      return partition(nums, start, right, k)
   }
   return nums[k]
}