题解 | #寻找第K大#

package main


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param a int整型一维数组
 * @param n int整型
 * @param K int整型
 * @return int整型
 */
func findKth(a []int, n int, K int) int {
	// write code here
	return a[findKthMaxIndex(a, 0, n-1, K-1)]
}
//数组按照从大到小进行排序
func partitionInverse(nums []int, l, r int) int {
	i, j := l, r
	for i < j {
		//从左到右找到第一个比pivot小的值
		for i < j && nums[i] > nums[l] {
			i++
		}
		//从右到左找到第一个比pivot大的值
		for i < j && nums[j] <= nums[l] {
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	nums[l], nums[i] = nums[i], nums[l]
	return i
}

func findKthMaxIndex(nums []int, l, r, k int) int {
	p := partitionInverse(nums, l, r)
	if p == k {
		return p
	}
	if p < k {
		return findKthMaxIndex(nums, p+1, r, k)
	}
	return findKthMaxIndex(nums, l, p-1, k)
}