本文介绍: topk问题一般分为两大类:第一大类就是找最大/最小的第k个元素,这一类只需要找一个元素即可。第二大类就是最大/最小的k个元素,这一类是找一串数字。在有上面的知识后,我们先解决第一类问题如何找第k个元素。
前言:
我们首先要明白什么是三路快排,什么是topk问题。
三路快排:
思想:
三路快排就是数组分3块,三个指针,先随机取一个基准值key,然后将数组划分为3个部分:
【小于key】【等于key】【大于key】
此时key的值的位置就确定了,然后再递归遍历小于key部分,和大于key的部分。
具体实现:根据nums[i]的值分类讨论
优化:用随机的方式选择基准元素
原码:
第二个问题:什么是topk问题?
第一类问题:
题目描述:
解法:
原码:
再解决第二类问题:
题目描述:
解法:
原码:
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。