周末读物之聊聊三观

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 1767|回复: 9
收起左侧

[算法题] 求问关于k个最小元素

[复制链接] |试试Instant~
我的人缘0
kingiori1 发表于 2016-10-24 02:25:29 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
quick select是O(n)但好像edge case很多,求问其他方法。

上一篇:求一道题思路
下一篇:图论题目的准备
我的人缘0
QDkAc 发表于 2016-10-25 13:13:02 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (83)
 
 
0% (0)  踩
找到前k小(大)的和找第k小是等价的。因为有了第k小(大)元素x后,你可以O(n) scan一下整个数组找到所有比x小(大)的元素就行了。
回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
stellari 发表于 2016-10-24 02:57:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (366)
 
 
1% (4)  踩
你是要找“最小的k个元素”还是“第k个最小元素”?
回复

使用道具 举报

我的人缘0
 楼主| kingiori1 发表于 2016-10-24 06:54:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩
stellari 发表于 2016-10-24 02:57
你是要找“最小的k个元素”还是“第k个最小元素”?

最小的k个
回复

使用道具 举报

我的人缘0
stellari 发表于 2016-10-24 10:14:06 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (366)
 
 
1% (4)  踩

Quickstart是最佳方法。而且实现起来并不难,和quicksort差不多。其他方法比如用heap之类的只能达到O(nlogk)的复杂度。我觉得你还是认真地看一下quickselect的实现比较好。其实并没有什么edge case需要额外处理,唯一的问题是在partition的时候可能要需要弄清swap的规则,这时可能涉及到许多case,但是这些case可以用一段简单的代码涵盖之。网上应该有不少quickselect的实现,你不妨查阅一下。

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
QDkAc 发表于 2016-10-25 13:10:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (83)
 
 
0% (0)  踩
refer to nth_element in <algorithm>
回复

使用道具 举报

我的人缘0
Badger96 发表于 2016-10-25 13:41:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (165)
 
 
0% (0)  踩
楼主可以去参考lc 215的第二高票回答,求最小只不过是把几个大于小于换过来
回复

使用道具 举报

我的人缘0
OO0OO 发表于 2016-10-26 04:35:45 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (114)
 
 
5% (6)  踩
今天刚看quick select,没有edge case的,implement也不难,我来复制粘贴也算记录一下:

因为求k个最小和第k个最小是同样的:

我们可以使用分而治之的方法来解决这一问题。如果将全部元素划分为两个子序列A和B,使得A中的全部元素都小于等于B中的任何元素,我们就可按照下面的方法减小问题的规模:

1. 比较子序列A的长度和k的大小;

2. 若k <= |A|,则第k小的元素必然在A中,我们可以丢弃子序列B,然后在A中进一步查找;
3. 若|A| < k,则第k小的元素必然在B中,我们可以丢弃子序列A,然后在B中进一步查找第(k − |A|)小的元素。

注意下划线部分强调了递归的特性。理想情况下,我们总是将序列划分为相 等长度的两个子序列A和B,这样每次都将问题的规模减半,因此性能为线性时 间O(n)。


关键问题是如何实现划分,将前m小的元素放入一个子序列中,将剩余元素放入另一个中。
回忆快速排序中的划分算法,它将所有小于pivot的元素移动到前面,将大于pivot的元素移动到后面。根据这一思路,我们可以构造一个分而治之的k选 择算法,称为“快速选择算法”。


1. 随机选择一个元素(例如第一个)作为pivot;

2. 将所有不大于pivot的元素放入子序列A;将剩余元素放入子序列B;

3. 比较A的长度和k,若|A| = k − 1,则pivot就是第k小的元素;

4. 若|A| > k − 1,递归在A中寻找第k小的元素;

5. 否则,递归在B中寻找第(k − 1 − |A|)小的元素;


我觉得这个讲的很清楚,摘自<初等算法>.

然后Quickselect也写的蛮好, implement 也不难

写一个partition函数和select函数,这里有很多代码可供参考  https://rosettacode.org/wiki/Quickselect_algorithm

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘1
shiloh00 发表于 2016-10-26 04:51:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  70% (1016)
 
 
29% (427)  踩
quickselect 没什么corner case啊 这是找第k大的代码 找到这个把前k个输出出来就是前k大的了

class Solution {
public:
    int helper(vector<int>& nums, int start, int end, int k) {
        if(end <= start)
            return nums[start];
        int idx = start;
        for(int i = start; i <= end; i++) {
            if(nums[i] <= nums[end]){
                swap(nums[i], nums[idx]);
                idx++;
            }
            idx--;
        }
        if(idx == k)
            return nums[idx];
    }
    int findKthLargest(vector<int>& nums, int k) {
        return helper(nums, 0, nums.size(), k - 1);
    }
};
回复

使用道具 举报

我的人缘0
adoria 发表于 2016-11-4 11:11:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
quickselect 是estimate case O(n),不是worst case O(n),要worst case O(n)右转median of median
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-22 09:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表