题解 | #寻找第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
}

func partition(nums []int, left, right int) int {
	// 基准, 比基准小的元素移动到基准的左边，比基准大的元素移动到基准的右边
	pivot := nums[left]
	l, r := left+1, right
	for l <= r {
		if nums[r] > pivot {
            r--
        }else{
            nums[l], nums[r] = nums[r], nums[l]
            l++
        }
	}
	nums[left], nums[l-1] = nums[l-1], nums[left]
	return l - 1
}