热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

LeetCode215:TopKLargestElementsEfficientlyExplained

本文详细解析了LeetCode第215题,即高效寻找数组中前K个最大元素的问题。通过使用快速选择算法(partition),可以在平均时间复杂度为O(N)的情况下完成任务。本文不仅提供了算法的具体实现步骤,还深入探讨了partition算法的工作原理及其在不同场景下的应用,帮助读者更好地理解和掌握这一高效算法。

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

程序看着比较奇怪,因为我是找的前k大,然后再找前k大里面最小的,之所以这样是为了复用之前 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 := len(prices)
stack := make([]pair, n)
profits := make([]int, 0, n)
v := 0
p := -1
top := 0
for true {
for v = p + 1; v+1 = prices[v+1]; v++ {
}
for p = v; p+1 1]; p++ {
}
//fmt.Println(v,p)
if v == 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...)
}



推荐阅读
author-avatar
手机用户2602929101
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有