画图 / 变量,区间定义 / 伪代码
分区的操作和快排一模一样
这里的伪代码实际找的是第k-1小的数 , 因此在这里做了转换
第k大的数 = 第len-k+1小的数 len=end+1
然后实际是找第k-1索引处的数 , 因此为end+1-k+1-1
(其实这里的定义有点混乱了 , 不管怎样第一次Accepted了 , 之后再改进 )
LeetCode Kth Largest Element in an Array
结果
func partition(nums []int, start int, end int) int {
p := start
j := start + 1
i := start
v := nums[p]
for j <= end {
if nums[j] < v {
tmp1 := nums[j]
nums[j] = nums[i+1]
nums[i+1] = tmp1
i++
j++
} else if nums[j] >= v {
j++
}
}
tmp2:=nums[i]
nums[i]=nums[p]
nums[p]=tmp2
p=i
return p
}
func findKthLargest(nums []int, k int) int {
start:=0
end:=len(nums)-1
//实际找的是第k-1小的数 , 因此在这里做了转换
//第k大的数 = 第len-k+1小的数 len=end+1
//然后实际是找第k-1索引处的数 , 因此为end+1-k+1-1
return findKthLargestIn(nums,start,end,end+1-k+1-1)
}
func findKthLargestIn(nums []int, start int, end int, n int) int{
k:=partition(nums,start,end)
if k==n {
return nums[k]
}
if k<n {
return findKthLargestIn(nums,k+1,end,n)
}
if k>n {
return findKthLargestIn(nums,start,k-1,n)
}
return 0
}
