题解 | #寻找第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
	K = n - K // 第k大的数在排序数组中索引为 n - k 的位置
	left, right := 0, n-1
	for left <= right {
		privotIndex := partition(a, left, right)
		// privotIndex == len - k  即当前为第K个大元素
		// privotIndex < len - k   在[privoteIndex + 1,right]中继续查找
		// privotIndex > len - k   在[left,privoteIndex - 1]中继续查找
		if privotIndex == K {
			return a[privotIndex]
		} else if privotIndex < K {
			left = privotIndex + 1
		} else {
			right = privotIndex - 1
		}
	}
	return -1
}

// partition 函数使用数组的第一个元素作为基准
func partition(a []int, left, right int) int {
	pivot := a[left] // 使用第一个元素作为基准
	i := left + 1    // 从基准的下一个元素开始
	for j := right; j >= i; {
		if a[j] > pivot { // 当找到一个大于基准的元素时，将它保持在右边
			j--
		} else {
			// 小于等于基准的元素移动到左边
			a[i], a[j] = a[j], a[i]
			i++
		}
	}
	// 最后，将基准元素移动到正确的位置
	a[left], a[i-1] = a[i-1], pivot
	return i - 1 // 返回基准元素的最终位置
}