好学生是生出来的，不是教出来的 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Parenting - 为人父母

好学生是生出来的，不是教出来的

好学生是生出来的，不是教出来的# Parenting - 为人父母

c*r2014-05-19 07:05

1 楼

这题到底具体应该怎么解啊？临近面试发现又什么都不会了。。。。
有N个pointer指向N个array的头，然后binary search这N个element然后找到最大的
insert到heap.
time complexity :O(logN*totallength)
或者直接建一个k size maxheap,然后insert所有元素
time complexity : O(logK*totallength)

j*c2014-05-19 07:05

2 楼

都是生出来的，跟家长老师怎么教没多大关系

r*a2014-05-19 07:05

3 楼

你的第一个做法，这N个头不是有序的，怎么binary search? 必须线性时间才能找到最
大的吧.

S*e2014-05-19 07:05

4 楼

咳咳，好学生肯定是可以教出来的。只不过教出来一个好学生有用没用就不一定了。

【在 j****c 的大作中提到】

: 都是生出来的，跟家长老师怎么教没多大关系

o*d2014-05-19 07:05

5 楼

maintain a heap of size N, insert all first elements of arrays.
each time, extract the largest one and insert the next element in the same
array
time complexity O(K logN)
any better solution?

【在 c*******r 的大作中提到】

: 这题到底具体应该怎么解啊？临近面试发现又什么都不会了。。。。
: 有N个pointer指向N个array的头，然后binary search这N个element然后找到最大的
: insert到heap.
: time complexity :O(logN*totallength)
: 或者直接建一个k size maxheap,然后insert所有元素
: time complexity : O(logK*totallength)

j*c2014-05-19 07:05

6 楼

顶多教教生活习惯这些东西
学习成绩完全看天分。天分好的，不用教能考95，好好教一下能提高到97；天分一般的
，再怎么教也就是从80提高到88

【在 S***e 的大作中提到】

: 咳咳，好学生肯定是可以教出来的。只不过教出来一个好学生有用没用就不一定了。

r*h2014-05-19 07:05

7 楼

1.找最大K个的话应该是minHeap吧？每次pop掉最小的
2.这个应该和外排序的N way merge一样吧？可以用tournament tree或者heap，不过
heap的size应该是2N-1

【在 o****d 的大作中提到】

: maintain a heap of size N, insert all first elements of arrays.
: each time, extract the largest one and insert the next element in the same
: array
: time complexity O(K logN)
: any better solution?

m*n2014-05-19 07:05

8 楼

只要能进腾校，一生过得开心，管他是生出来的还是教出来的呢？

【在 j****c 的大作中提到】

: 顶多教教生活习惯这些东西
: 学习成绩完全看天分。天分好的，不用教能考95，好好教一下能提高到97；天分一般的
: ，再怎么教也就是从80提高到88

a*32014-05-19 07:05

9 楼

对N个数组中的最大元素开始做二分，找到一个最小的m，是的N个数组中恰好有>=k个数
小于等于m，那么m就是所求。
每次求N个数组中多少个元素小于等于m，nlogn，最多二分32或者64次（取决于数据是
32位还是64位），这样看的话是nlogn的，只不过常数有点大
如果不认为这个实常数，那么就是nlog(n)log(max_value-min_value)
klogn的问题是，k可能很大，如果k~n^2/2，那复杂度就高上去了

M*k2014-05-19 07:05

10 楼

前两者有什么必然联系么？

【在 m******n 的大作中提到】

: 只要能进腾校，一生过得开心，管他是生出来的还是教出来的呢？

r*h2014-05-19 07:05

11 楼

那使用一个大小为k的heap呢
第一次取第一个数组中的前k个元素，如果长度小于k的话就取第二个数组，直到取到k
个元素建堆。然后顺序处理每个数组前k个元素，更新这个堆。总时间应该是
O(nk * log k)。不过在总元素数量非常大内存装不下的时候，这种方法的I/O次数比O(
k log n)的方法少。
绕晕了。。。求指导

【在 a*******3 的大作中提到】

: 对N个数组中的最大元素开始做二分，找到一个最小的m，是的N个数组中恰好有>=k个数
: 小于等于m，那么m就是所求。
: 每次求N个数组中多少个元素小于等于m，nlogn，最多二分32或者64次（取决于数据是
: 32位还是64位），这样看的话是nlogn的，只不过常数有点大
: 如果不认为这个实常数，那么就是nlog(n)log(max_value-min_value)
: klogn的问题是，k可能很大，如果k~n^2/2，那复杂度就高上去了

S*e2014-05-19 07:05

12 楼

哦，那这得看你怎么定义好学生。要是top 1%，那的确不可能把大部分人都教成top 1%
。要是得A就算，那很多都是教出来的。

【在 j****c 的大作中提到】

: 顶多教教生活习惯这些东西
: 学习成绩完全看天分。天分好的，不用教能考95，好好教一下能提高到97；天分一般的
: ，再怎么教也就是从80提高到88

o*o2014-05-19 07:05

13 楼

既然是sorted（假设是从大到小），就用一个size n的最大堆，每次取出最大的，然后
加入该元素所在数组的后续元素，heapify之后再取，直到取到top K停止。
如果不是sorted，那就得用size k的最小堆，遍历所有array的剩余元素，分别与最小
堆的root比较，大于root就替换root，heapify一下，小于等于就跳过。

a*y2014-05-19 07:05

14 楼

你是好学生吗，如果不是，你是从那儿来的。如果是，你有多么好呢？

【在 j****c 的大作中提到】

: 都是生出来的，跟家长老师怎么教没多大关系

D*d2014-05-19 07:05

15 楼

到底是 k >> N 还是 N << k?
如果 N array 连头元素的排序也没有，那至少要建个 size k 的 heap 来排头元素啊,
这样要 N*lgk, 剩下还要 k*lgk 找出前k个

a*y2014-05-19 07:05

16 楼

你是好学生吗，如果不是，你是从那儿来的。如果是，你有多么好呢？

【在 j****c 的大作中提到】

: 都是生出来的，跟家长老师怎么教没多大关系

q*z2014-05-19 07:05

17 楼

根据三楼的做法，用C++写了一个，根据STL的文档应该是O(N+K)的时间复杂度，空间复
杂度不太清楚：
vector topK(vector> arrs, int N, int K)
{
priority_queue a;
unordered_multimap idxs;
for(int i = 0; i < N; i++)
{
if(!arrs[i].empty())
{
idxs.insert(make_pair(arrs[i].back(),i));
a.push(arrs[i].back());
arrs[i].pop_back();
}
}
vector r;
for(int i = 0; i < K; i++)
{
int val = a.top();
a.pop();
r.push_back(val);
auto it = idxs.find(val);
int k = it->second;
idxs.erase(it);
if(!arrs[k].empty())
{
idxs.insert(make_pair(arrs[k].back(),k));
a.push(arrs[k].back());
arrs[k].pop_back();
}
}
return r;
}

a*y2014-05-19 07:05

18 楼

我咋觉得进腾校反而过得不开心呢。看那老墨们，有几个腾校混过，干得收入最低的工
作，政府养着，比谁都开心

【在 m******n 的大作中提到】

: 只要能进腾校，一生过得开心，管他是生出来的还是教出来的呢？

c*r2014-05-19 07:05

19 楼

还是没搞懂。如果是N个sorted array...是应该建大小为k的max heap么？然后每个
array的指针往heap里insert，都和root比，如果比root大的话就更换

I*e2014-05-19 07:05

20 楼

haha

【在 m******n 的大作中提到】

: 只要能进腾校，一生过得开心，管他是生出来的还是教出来的呢？

c*r2014-05-19 07:05

21 楼

还是没搞懂。如果是N个sorted array...是应该建大小为k的max heap么？然后每个
array的指针往heap里insert，都和root比，如果比root大的话就更换

I*e2014-05-19 07:05

22 楼

老墨开心不是因为没进藤校
老中进藤校的不进的开心的几率大

【在 a*****y 的大作中提到】

: 我咋觉得进腾校反而过得不开心呢。看那老墨们，有几个腾校混过，干得收入最低的工
: 作，政府养着，比谁都开心

o*d2014-05-19 07:05

23 楼

why it is O(N+K)
do you mean the amortized complexity?
I understand that if it the heap is implemented as a Fibonacci heap, the
complexity of insert is amortized O(1), extract can also O(1)

【在 q*******z 的大作中提到】

: 根据三楼的做法，用C++写了一个，根据STL的文档应该是O(N+K)的时间复杂度，空间复
: 杂度不太清楚：
: vector topK(vector> arrs, int N, int K)
: {
: priority_queue a;
: unordered_multimap idxs;
: for(int i = 0; i < N; i++)
: {
: if(!arrs[i].empty())
: {

s*12014-05-19 07:05

24 楼

教坏太容易了

q*z2014-05-19 07:05

25 楼

因为所有操作都是O(1)啊，STL 的priority queue的操作都是O(1),hash table 也是O(
1)

【在 o****d 的大作中提到】

: why it is O(N+K)
: do you mean the amortized complexity?
: I understand that if it the heap is implemented as a Fibonacci heap, the
: complexity of insert is amortized O(1), extract can also O(1)

s*32014-05-19 07:05

26 楼

要肯定后天的教育重要，不然要学校干嘛

o*d2014-05-19 07:05

27 楼

yes, O(1) should be amortized time cost, including hashtable.

O(

【在 q*******z 的大作中提到】

: 因为所有操作都是O(1)啊，STL 的priority queue的操作都是O(1),hash table 也是O(
: 1)

g*n2014-05-19 07:05

28 楼

可惜你不是劳模，过不了穷开心的日子

【在 a*****y 的大作中提到】

: 我咋觉得进腾校反而过得不开心呢。看那老墨们，有几个腾校混过，干得收入最低的工
: 作，政府养着，比谁都开心

d*32014-05-19 07:05

29 楼

不对吧，prioriy queue push 操作是logn的

O(

【在 q*******z 的大作中提到】

: 因为所有操作都是O(1)啊，STL 的priority queue的操作都是O(1),hash table 也是O(
: 1)

j*c2014-05-19 07:05

30 楼

学校里学生也分三六九等不是？钥匙学校教育有用，应该教出来一样的，差异来自于基因

【在 s******3 的大作中提到】

: 要肯定后天的教育重要，不然要学校干嘛

s*32014-05-19 07:05

31 楼

内因外因共同作用下的结果有什么奇怪的吗？
石头自然孵不出小鸡但只有鸡蛋也不会有小鸡
很复杂的道理吗

基因

【在 j****c 的大作中提到】

: 学校里学生也分三六九等不是？钥匙学校教育有用，应该教出来一样的，差异来自于基因

j*c2014-05-19 07:05

32 楼

聪明的学生在大学都是自学的好不好？

【在 s******3 的大作中提到】

: 内因外因共同作用下的结果有什么奇怪的吗？
: 石头自然孵不出小鸡但只有鸡蛋也不会有小鸡
: 很复杂的道理吗
:
: 基因

k*b2014-05-19 07:05

33 楼

'老中进藤校的不进的开心'，家长不开心，还是孩子不开心?
孩子不开心，大半也是家长教育出来的。
家长应该manage自己对孩子期望。。

【在 I*****e 的大作中提到】

: 老墨开心不是因为没进藤校
: 老中进藤校的不进的开心的几率大

j*c2014-05-19 07:05

34 楼

呵呵，老中对孩子的期望只会变高不会降低
有哪个老中觉得自己的娃不是天才？

【在 k******b 的大作中提到】

: '老中进藤校的不进的开心'，家长不开心，还是孩子不开心?
: 孩子不开心，大半也是家长教育出来的。
: 家长应该manage自己对孩子期望。。

s*e2014-05-19 07:05

35 楼

基因非常强大，必须承认。但高智商的娃如果不好好教育，学坏也快。

【在 j****c 的大作中提到】

: 都是生出来的，跟家长老师怎么教没多大关系

t*c2014-05-19 07:05

36 楼

好学生是生出来的，我同意。
但是最后成功的人，都是执著的人，而不一定是聪明的人或者好学生。
所以我觉得学校教育关键在于获得基本知识和技能，为今后的执著提供一个素质基础。
而是不是好学生，或者换句话说，是不是top student, 不重要。

【在 j****c 的大作中提到】

: 都是生出来的，跟家长老师怎么教没多大关系