T******7
发帖数: 1419 | 1 给一个数组， 找最大的整数m， 使得数组里比m大的或相等
的值的树木大于等于m（线性） |
T******7
发帖数: 1419 | 2 这题目 不排序，不用heap怎么解o(n)的算法？ |
a******g
发帖数: 13519 | 3 排序好的数组？
【在 T******7 的大作中提到】
: 这题目 不排序，不用heap怎么解o(n)的算法？
|
T******7
发帖数: 1419 | 4 of course not. Otherwise it is too easy.
【在 a******g 的大作中提到】
: 排序好的数组？
|
a******g
发帖数: 13519 | 5 这尼玛的解个毛，肯定被黑了。
【在 T******7 的大作中提到】
: of course not. Otherwise it is too easy.
|
d*******l
发帖数: 338 | 6 数组有n个元素的话，m可能的取值只能是0到n，把空间划分成n+2个区间统计一下原数
组落在各个区间的元素个数就能依次尝试了
【在 T******7 的大作中提到】
: of course not. Otherwise it is too easy.
|
s*******7
发帖数: 6 | 7 好聪明啊～～～～～～
【在 d*******l 的大作中提到】
: 数组有n个元素的话，m可能的取值只能是0到n，把空间划分成n+2个区间统计一下原数
: 组落在各个区间的元素个数就能依次尝试了
|
m****i
发帖数: 650 | 8 区间如何划分，不Practical？
【在 d*******l 的大作中提到】
: 数组有n个元素的话，m可能的取值只能是0到n，把空间划分成n+2个区间统计一下原数
: 组落在各个区间的元素个数就能依次尝试了
|
s*******1
发帖数: 33 | |
s*******1
发帖数: 33 | 10 应该用quicksort + binarySearch |
|
|
r****e
发帖数: 10 | 11 m应该在0-n/2的范围，用一个额外的n/2的数组。扫描一遍原数组，数值比n/2大的在额
外数组的[n/2-1]++,其它的对应的[v-1]++.然后倒序扫描额外数组，值比其索引大的第
一个就是答案。 |
x*******9
发帖数: 138 | 12 二分 + 快速划分
平均情况下是O(n)的，即每次都能平分数组。复杂度为O(n) + O(1/2 * n) + O(1/4 *
n)... => O(n)
最差情况是O(n * 2)，类似于快排的最差情况。 |
s******x
发帖数: 417 | 13 quicksort 怎么看都是O(nlgn）啊。。。 |
C********s
发帖数: 7 | 14 Didn't try to write it to be bug-free, but you get the idea:
int find_m(double* a, int length) {
int* counter = (int*)malloc(sizeof(int) * (length + 2));
for (int i = 0; i < length; i++) {
if (a[i] > length) {
counter[length + 1]++;
} else if (a[i] >= 0) {
counter[int(floor(a[i]))]++;
}
}
int sum = 0;
for (int i = length + 1; i>= 0; i--) {
sum += counter[i];
if (sum == i) return i;
}
} |
c**y
发帖数: 172 | 15 does the solution always exist for any array? What is the result for the
array {101, 102}? |
t*8
发帖数: 14 | 16 这样做的话，如何区分{100,101,102,103}和{100,100,100,100}两种情况？
【在 d*******l 的大作中提到】
: 数组有n个元素的话，m可能的取值只能是0到n，把空间划分成n+2个区间统计一下原数
: 组落在各个区间的元素个数就能依次尝试了
|
s*****4
发帖数: 2 | 17 这个是h-index吧，我记得好像是可以O(N)的，存个数组 |
b***e
发帖数: 1419 | 18 这个不就是个counting sort么。比n大的不用排，直接搞个变量计数就行了。
【在 T******7 的大作中提到】
: 这题目 不排序，不用heap怎么解o(n)的算法？
|
a***u
发帖数: 383 | 19 如果都是整数的话应该是counting sort |
d******v
发帖数: 801 | 20 我觉得｛0｝是例外，找不到合适的m
【在 c**y 的大作中提到】
: does the solution always exist for any array? What is the result for the
: array {101, 102}?
|
b***e
发帖数: 1419 | 21 100个100?
【在 r****e 的大作中提到】
: m应该在0-n/2的范围，用一个额外的n/2的数组。扫描一遍原数组，数值比n/2大的在额
: 外数组的[n/2-1]++,其它的对应的[v-1]++.然后倒序扫描额外数组，值比其索引大的第
: 一个就是答案。
|
r****e
发帖数: 10 | 22 这是个好例子，不过算法不用变，只是需要o(n)的额外空间。
【在 b***e 的大作中提到】
: 100个100?
|
