LeetCode215:TopKLargestElementsEfficientlyExplained

这种前几大的题通通用partition就可以在O(N)时间内解决&＃xff0c;之所以要特意写个题解是因为想把partition的算法记下来&＃xff0c;每次写都写得很纠结

程序看着比较奇怪&＃xff0c;因为我是找的前k大&＃xff0c;然后再找前k大里面最小的&＃xff0c;之所以这样是为了复用之前 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/ 的函数

type pair struct {
v int
p int
}func maxProfit(k int, prices []int) int {
n :&＃61; len(prices)
stack :&＃61; make([]pair, n)
profits :&＃61; make([]int, 0, n)
v :&＃61; 0
p :&＃61; -1
top :&＃61; 0
for true {
for v &＃61; p &＃43; 1; v&＃43;1 &＃61; prices[v&＃43;1]; v&＃43;&＃43; {
}
for p &＃61; v; p&＃43;1 1]; p&＃43;&＃43; {
}
//fmt.Println(v,p)
if v &＃61;&＃61; p {
break
}
/*case 1, do nothing but pop the last vp pair and put them into the profit array
/
for top > 0 && prices[v] <&＃61; prices[stack[top-1].v] {
profits &＃61; append(profits, prices[stack[top-1].p]-prices[stack[top-1].v])
top--
}
/case 2, merge the two vp pairs
*/
for top > 0 && prices[p] >&＃61; prices[stack[top-1].p] {
profits &＃61; append(profits, prices[stack[top-1].p]-prices[v])
v &＃61; stack[top-1].v
top--
}
stack[top] &＃61; pair{v: v, p: p}
top&＃43;&＃43;
}
for top > 0 {
profits &＃61; append(profits, prices[stack[top-1].p]-prices[stack[top-1].v])
top--
}
ans :&＃61; 0
//fmt.Println(profits)
if len(profits) <&＃61; k {
ans &＃61; accumulate(profits)
return ans
}
ans &＃61; accumulate(firstKLargest(profits, k))
return ans}func accumulate(arr []int) int{
n :&＃61; len(arr)
ans :&＃61; 0
for i :&＃61; 0; i ans &＃43;&＃61; arr[i]
}
return ans
}func firstKLargest(slice []int, k int) []int {
length :&＃61; len(slice)if length <&＃61; k {return slice
}m :&＃61; slice[rand.Intn(length)]less :&＃61; make([]int, 0, length)
more :&＃61; make([]int, 0, length)
equal :&＃61; make([]int, 0, length)for _, item :&＃61; range slice {switch {case item append(less, item)case item > m:more &＃61; append(more, item)default :equal &＃61; append(equal, item)}
}
if len(more) > k {return firstKLargest(more, k)
} else if len(more) &＃61;&＃61; k {return more
}else if len(more) &＃43; len(equal) >&＃61; k{more &＃61; append(more, equal[:k-len(more)]...)//fmt.Println("debug more",more)return more
}
more &＃61; append(more, equal...)
// fmt.Println("Less", less)
// fmt.Println("More", more)
// fmt.Println("Equal", equal)
part :&＃61; firstKLargest(less, k-len(more))
return append(part, more...)
}