215. 数组中的第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 <= 10⁵
• -10⁴ <= nums[i] <= 10⁴

题解

先对数组进行逆序排序，然后找到第 K 个元素。
这里对数组排序使用的是归并排序方法。

代码实现

func findKthLargest(nums []int, k int) int {
	nums = mergeSort(nums)
	return nums[k-1]
}

func mergeSort(nums []int) []int {
	if len(nums) < 2 {
		return nums
	}
	mid := len(nums) / 2
	left := mergeSort(nums[:mid])
	right := mergeSort(nums[mid:])
	return merge(left, right)
}

func merge(left, right []int) []int {
	l, r := len(left), len(right)
	i, j := 0, 0
	var res []int
	for i < l && j < r {
		if left[i] > right[j] {
			res = append(res, left[i])
			i++
		} else {
			res = append(res, right[j])
			j++
		}
	}

	for i < l {
		res = append(res, left[i])
		i++
	}
	for j < r {
		res = append(res, right[j])
		j++
	}
	return res
}