e**********y
发帖数: 128 | 1 在这个版得到好多帮助，现在贡献刚刚A家的3道题目
1. 单链表是否有环
2. 找到一个数组中的 频率最高的数 比如，Array[2, 2, 3, 1], 频率最高的 是2.
3. 找到链表中离原点最近的k个点 |
c********p
发帖数: 1969 | |
c********p
发帖数: 1969 | 3 3题什么意思？原点是（0,0）? 还是head? |
e**********y
发帖数: 128 | 4 每个点都有x，y坐标，原点是指点（0，0）， 求离原点最近的k个点。我尽量避免英文
，省的，让人google到。
【在 c********p 的大作中提到】
: 3题什么意思？原点是（0,0）? 还是head?
|
c********p
发帖数: 1969 | 5 太聪明了，不要用英文的！
【在 e**********y 的大作中提到】
: 每个点都有x，y坐标，原点是指点（0，0）， 求离原点最近的k个点。我尽量避免英文
: ，省的，让人google到。
|
C****y
发帖数: 581 | 6 第二题最优解是什么？hashtable?
第三题？ |
h**6
发帖数: 4160 | |
c********p
发帖数: 1969 | 8 第3题怎么做？
我能想到的就是，过一遍，用个hashtable存对应坐标和离原点距离，同时把距离放到
一个array里。
array sort的话，O(nlgn), 然后找出来前k个，再对应hashtable里的坐标。
或者用quick select 在array里找前k个，然后对应hashtable的坐标。。。
但这个方法貌似好麻烦啊。有简单的么？ |
J****3
发帖数: 427 | |
J****3
发帖数: 427 | 10 或者median in median partition 也行吧 |
|
|
u*****o
发帖数: 1224 | 11 先BLESS LZ飞速拿到ONSITE，然后坐下来慢慢看。。 |
u*****o
发帖数: 1224 | 12 第二题可以用MULTIMAP里的COUNT吗？先建TABLE，然后扫一遍，记录MAXCOUNT？
【在 e**********y 的大作中提到】
: 在这个版得到好多帮助，现在贡献刚刚A家的3道题目
: 1. 单链表是否有环
: 2. 找到一个数组中的 频率最高的数 比如，Array[2, 2, 3, 1], 频率最高的 是2.
: 3. 找到链表中离原点最近的k个点
|
c********p
发帖数: 1969 | 13 对哦，但具体怎么做呢？
因为比较的是距离，而给的是坐标，就算heap放的是距离，找到这些值之后，不是还要
重新遍历一遍找坐标啊？
【在 J****3 的大作中提到】
: 维护一个size k 的最小堆
|
l*******A
发帖数: 209 | 14 第二道要是数组的值限制在一个范围内,可以counting sort
或者扫一遍然后加入Map,然后遍历一次找max value
还有更好的方法么?
【在 e**********y 的大作中提到】
: 在这个版得到好多帮助，现在贡献刚刚A家的3道题目
: 1. 单链表是否有环
: 2. 找到一个数组中的 频率最高的数 比如，Array[2, 2, 3, 1], 频率最高的 是2.
: 3. 找到链表中离原点最近的k个点
|
l*******A
发帖数: 209 | 15 第三题建个最小堆
然后remove top element k times?
【在 e**********y 的大作中提到】
: 在这个版得到好多帮助，现在贡献刚刚A家的3道题目
: 1. 单链表是否有环
: 2. 找到一个数组中的 频率最高的数 比如，Array[2, 2, 3, 1], 频率最高的 是2.
: 3. 找到链表中离原点最近的k个点
|
k*******t
发帖数: 144 | 16 感觉应该建立个max heap, 每次比较某点距离dist和top of max heap,
if dist < max_heap.top, then pop max_heap, push dist;
else ignore, do nothing;
最后得到的就是k smallest distances啦
【在 l*******A 的大作中提到】
: 第三题建个最小堆
: 然后remove top element k times?
|
J****3
发帖数: 427 | 17 恩 对的
【在 k*******t 的大作中提到】
: 感觉应该建立个max heap, 每次比较某点距离dist和top of max heap,
: if dist < max_heap.top, then pop max_heap, push dist;
: else ignore, do nothing;
: 最后得到的就是k smallest distances啦
|
l*******0
发帖数: 63 | 18 第二题 是否还有别的条件？比如说要找的数出现次数保证超过一半？1/3或者1/4之类
的?
【在 e**********y 的大作中提到】
: 在这个版得到好多帮助，现在贡献刚刚A家的3道题目
: 1. 单链表是否有环
: 2. 找到一个数组中的 频率最高的数 比如，Array[2, 2, 3, 1], 频率最高的 是2.
: 3. 找到链表中离原点最近的k个点
|
f*******b
发帖数: 520 | 19 Problem 3:
Using Min heap：
1. Create a pair list(key:distance;value:coordinate). O(n)
2. Build a Min heap based on key. O(n)
3. Get values of the first Ks of key from Min heap. O(K)
Time complexity: O(n)
【在 k*******t 的大作中提到】
: 感觉应该建立个max heap, 每次比较某点距离dist和top of max heap,
: if dist < max_heap.top, then pop max_heap, push dist;
: else ignore, do nothing;
: 最后得到的就是k smallest distances啦
|
p*****2
发帖数: 21240 | |
|
|
i****y
发帖数: 84 | 21 quick select复杂度是O(kn)吗？maxheap是O(n)吗？
【在 p*****2 的大作中提到】
: 第三题为什么不用quick select？
|
p*****2
发帖数: 21240 | 22
是O(n)
【在 i****y 的大作中提到】
: quick select复杂度是O(kn)吗？maxheap是O(n)吗？
|
s***5
发帖数: 2136 | 23 maxheap
【在 f*******b 的大作中提到】
: Problem 3:
: Using Min heap：
: 1. Create a pair list(key:distance;value:coordinate). O(n)
: 2. Build a Min heap based on key. O(n)
: 3. Get values of the first Ks of key from Min heap. O(K)
: Time complexity: O(n)
|
s***5
发帖数: 2136 | 24 quick select需要把所有distince存在一个array里，需要额外的O(n)空间吧。
【在 p*****2 的大作中提到】
: 第三题为什么不用quick select？
|
p*****2
发帖数: 21240 | 25
其实也不需要。做个comparator就可以了。
【在 s***5 的大作中提到】
: quick select需要把所有distince存在一个array里，需要额外的O(n)空间吧。
|
