Redian新闻
>
marriott chase card 的那个一晚上免费怎么订?
avatar
marriott chase card 的那个一晚上免费怎么订?# Money - 海外理财
l*h
1
从一堆没有排序的整数中找出最大的K个.
avatar
x*n
2
是从Marriottt网上订吗? 我只看到开卡的点数, 没有看到那个免费一晚的。
多谢!
avatar
j*y
3
selection sort

【在 l**h 的大作中提到】
: 从一堆没有排序的整数中找出最大的K个.
avatar
w*w
4
登陆Marriott账户-account information-Unused Certificates
baozi plz
avatar
p*p
5
这是O(nk)的

【在 j*****y 的大作中提到】
: selection sort
avatar
m*w
6
或者打电话

【在 x****n 的大作中提到】
: 是从Marriottt网上订吗? 我只看到开卡的点数, 没有看到那个免费一晚的。
: 多谢!

avatar
j*y
7
select the (n-k)th element in the array, which is linear

【在 p*****p 的大作中提到】
: 这是O(nk)的
avatar
m*1
8
这样行不行,开一个数组,长度为k,每次把这堆数扫一遍,取出最大的,放到数组中
,然后置为负,然后又继续扫,又取出当前最大的,直到找到了k个,这样复杂度是O(
KN),从数量级上还是O(n)。。。。
avatar
s*0
9
no way
if it is doable, the worst case of qicksort will be O(nlogn).

【在 l**h 的大作中提到】
: 从一堆没有排序的整数中找出最大的K个.
avatar
p*p
10
The array is not sorted so not possible to get that in linear time
qsort can do that in amortized O(n) but not worst case

【在 j*****y 的大作中提到】
: select the (n-k)th element in the array, which is linear
avatar
j*y
11
It can. just google "selection sort" :)

【在 p*****p 的大作中提到】
: The array is not sorted so not possible to get that in linear time
: qsort can do that in amortized O(n) but not worst case

avatar
r*n
12
可以,
result = []
1 left, right = partition // the elements in right > that of left
2 if sizeof(right) > k
drop the left, recursively call on the right.
else if sizeof(right) < k
k = k - sizeof(right)
append the right to the result.
recursively call on the left.
else
append the right to the result.
the end.


【在 s****0 的大作中提到】
: no way
: if it is doable, the worst case of qicksort will be O(nlogn).

avatar
p*p
13
that takes n + n - 1 + ... + n - k - 1 which is O(nk)

【在 j*****y 的大作中提到】
: It can. just google "selection sort" :)
avatar
S*t
15
First select the $K+1$-th element using the selection algorithm. This is $O(
n)$. And then use that element to partition. That's $O(n)$ as well.
avatar
j*y
16
不是这么做的。
先找到第 n-k大的数 r,这个时间代价是 linear,
这个 是 call selection_sort(n, n-k)
然后扫描整个数组,比 r大的就留下, 这样就得到 k个最大的数了

【在 p*****p 的大作中提到】
: that takes n + n - 1 + ... + n - k - 1 which is O(nk)
avatar
p*2
17
这题还用讨论吗?上边好几个都说了。
avatar
s*0
18
真丢人。把median of medians给忘了。

【在 s****0 的大作中提到】
: no way
: if it is doable, the worst case of qicksort will be O(nlogn).

avatar
d*x
19
median of medians并不实用,常数过大无比缓慢,只是作为一种理论上的kth element
可被worst-case O(n)找到的实例。
quick selection的worst case是O(n^2),但是ramdomized之后效果很好,唯一问题是
它不是online算法,而且还要改原数组
所以在特定情形下heap也很好用,如果k相对于n是个很小的数

【在 s****0 的大作中提到】
: 真丢人。把median of medians给忘了。
avatar
b*g
20
Top k的问题是不是一般两种解法?
1.用heap sort的思路建一个大小为k的min heap
2.用selection rank,思路就类似quick sort
请问对吗?

【在 p*****2 的大作中提到】
: 这题还用讨论吗?上边好几个都说了。
avatar
l*h
21
according to wiki, selection sort is o(n^2).
If you only sort k element, it's still o(n*k), why you think its linear?

【在 j*****y 的大作中提到】
: It can. just google "selection sort" :)
avatar
S*t
22
$k$ is a constant.

【在 l**h 的大作中提到】
: according to wiki, selection sort is o(n^2).
: If you only sort k element, it's still o(n*k), why you think its linear?

avatar
d*x
23
说中文吧。。。
他其实是想说quick selection,而不是selection sort

【在 l**h 的大作中提到】
: according to wiki, selection sort is o(n^2).
: If you only sort k element, it's still o(n*k), why you think its linear?

avatar
d*x
24
有区别么。。

avatar
w*p
25
没有大的区别,很传统的题啊。
但是做题前,总是要清楚题,才好把清晰完整的思路给出来。

【在 d**********x 的大作中提到】
: 有区别么。。
:
: 数

avatar
d*x
26
思路也是一样的。。。

【在 w********p 的大作中提到】
: 没有大的区别,很传统的题啊。
: 但是做题前,总是要清楚题,才好把清晰完整的思路给出来。

avatar
A*e
27
我认为是这样的

【在 b****g 的大作中提到】
: Top k的问题是不是一般两种解法?
: 1.用heap sort的思路建一个大小为k的min heap
: 2.用selection rank,思路就类似quick sort
: 请问对吗?

avatar
r*o
28
我觉得一般面试就用selection sort的办法,复杂度O(nk),
当然这题可以用类似quick sort的方法,但是现场写出bug-free的代码基本上很难吧。

【在 l**h 的大作中提到】
: 从一堆没有排序的整数中找出最大的K个.
avatar
w*p
29
我个人认为我在解题前需要完全了解题目的意思。
就这样。

【在 d**********x 的大作中提到】
: 思路也是一样的。。。
avatar
w*p
30
我小小声的认为,这题一定要练习到用类似quick sort的二分法,然后bug-free的写出
来。
这题是基本题。比quicksort 简单。

【在 r****o 的大作中提到】
: 我觉得一般面试就用selection sort的办法,复杂度O(nk),
: 当然这题可以用类似quick sort的方法,但是现场写出bug-free的代码基本上很难吧。

avatar
d*x
31
难度基本一样
就一个partition可能会写错

吧。

【在 w********p 的大作中提到】
: 我小小声的认为,这题一定要练习到用类似quick sort的二分法,然后bug-free的写出
: 来。
: 这题是基本题。比quicksort 简单。

avatar
h*3
32
《算法导论》第九章。

【在 l**h 的大作中提到】
: 从一堆没有排序的整数中找出最大的K个.
avatar
l*z
33
可以用一个大小为k的heap,每次遇到大数插入heap,然后removeMin。
这样最后heap中是最大的k个数,O(nlogk)
avatar
e*s
34
min-heap是正解吧?
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。