S*******C
发帖数: 822 | 1 以下的O(n) time, O(1) space解法还能再简化吗？
Kth Largest Element
18%
Accepted
Find K-th largest element in an array.
Note
You can swap elements in the array
Example
In array [9,3,2,4,8], the 3rd largest element is 4
In array [1,2,3,4,5], the 1st largest element is 5, 2nd largest element is 4
, 3rd largest element is 3 and etc.
Challenge
O(n) time, O(1) space
class Solution {
public static void main(String args[]) {
Solution test = new Solution();
int[] a = { 5, 4, 1, 3, 2};
Arra... 阅读全帖 |
|
a*******y
发帖数: 1040 | 2 kth min简单，kth max 要是用inverted inorder的话，要是那个值在left tree里，这
样return回来的不对啊 |
|
|
|
b*****c
发帖数: 1103 | 5 不过最小是不表意的，因为kth最小和kth最大两种说法是同一意思。 |
|
b*****c
发帖数: 1103 | 6 不过最小是不表意的，因为kth最小和kth最大两种说法是同一意思。 |
|
i***n
发帖数: 216 | 7 【 以下文字转载自 EE 讨论区 】
发信人: innin (innin), 信区: EE
标 题: KTH （瑞典皇家理工学院）的信号处理怎么样？
发信站: BBS 未名空间站 (Mon Mar 2 19:02:52 2009)
老板说他认识KTH的人， 说哪里signal processing 不错. 我从来么有听说过这个学校
。。。
知道的大侠可以告诉我一些信息么？ |
|
r****o
发帖数: 1950 | 8 【 以下文字转载自 InterviewHackers 俱乐部 】
发信人: roufoo (五经勤向窗前读), 信区: InterviewHackers
标 题: The time complexity on finding the kth largest element in a
发信站: BBS 未名空间站 (Tue Jun 1 22:42:09 2010, 美东)
We can use the partition() in qsort. Each time, we can partition the array
into two parts, array_a and array_b. Let the number of elements in array_a
and array_b be sa and sb, respectively.
If sa is smaller than k, then find the (k-sa)th largest element in array_b;
If sa is larger than or equal to k, then find |
|
g***j
发帖数: 1275 | 9 请问，一般题目问kth smallest element的题目，是返回那个数字还是返回那个数字在
原来数组中的index？
这个题目肯定要打乱原来的数组的顺序吧？如果是要返回原来数组中的index，怎么办？ |
|
c**********e
发帖数: 2007 | 10 Design an algorithm to find the kth number such that the only prime factors
are 3, 5 and 7. |
|
w****o
发帖数: 2260 | 11 经常看到题目要求 kth largest or smallest,
到底 k 是从1还是从0开始的？
一方面觉得从1开始比较合理，比如 通常first largest,大概就是 指最大的数，就是
1th largest
另一方面，好像在C语言里面，一般来讲都是从0开始index的？
大家说说，大家是怎么理解的？面试的时候是怎么做的？ |
|
c*******a
发帖数: 35 | 12 从每个array里每次读一个数出来，建立一个min heap，每次取出heap的root，也就是
最小的，从这个root元素所在的array再取下一个元素，插入到heap中，直到找到第kth
个数。因此heap总是保持32个元素。 |
|
k******I
发帖数: 238 | 13 为啥Heap 总是保持32个元素？最后不应该是k个吗？
kth |
|
d**e
发帖数: 6098 | 14 还没仔细想，但如果kth min简单的话，那要是那个值在right tree是怎么处理？我觉
得min max应该是差不多解法吧 |
|
a******o
发帖数: 106 | 15 高手麻烦检查下代码C#
就像BST inorder 遍历一样， private method 传递 ref k 和 输出的node， 每次遍
历一个数 k-1, 如果k==0 输出当前node 就行。
Kth Min 和 Max 原理完全一样， 只不过把Inorder 的顺序变成 右节点先考虑而已
。
请大侠们批评指正， 谢谢
private static void findKthMinNodeInBST(BinaryTree.Node n, ref int k
, ref BinaryTree.Node outnode)
{
if (n == null) return;
findKthMinNodeInBST(n.Left, ref k, ref outnode);
k--;
if (k < 0) return;
if (k == 0)
{
outnode = n;
... 阅读全帖 |
|
d****o
发帖数: 1055 | 16 就像找linked list 离尾第k个串一样。设置2个int a b,当a走到第kth min value,然
后a,b同时走。 |
|
s***y
发帖数: 3042 | 17 为啥不同啊？我是新手，随便写个。
int printKth(Node *root, int *k) {
if( !root )
return 0;
int ret;
ret = printKth(root->right, k);
if(ret == -1)
return -1;
(*k)--;
if((*k)==0) {
cout << "the kth is " << root->data << endl;
return -1;
}
return printKth(root->left, k);
} |
|
g****y
发帖数: 240 | 18 贴个python版的
def findk(alist, blist, k):
"""Given two sorted array, find kth minimum element"""
m = len(alist)
n = len(blist)
assert (k <= m + n)
if m == 0:
return blist[k - 1]
elif n == 0:
return alist[k - 1]
if k == 1:
return min(alist[0], blist[0])
# divide k into two even parts as much as possible
ai = min(k // 2, m)
bi = k - ai
if bi > n:
bi = n
ai = k - bi
if alist[ai - 1] == blist[... 阅读全帖 |
|
c*****a
发帖数: 808 | 19 能跑啊，我试了一下，把那多余的system.out.print去掉就只显示kth了 |
|
w****x
发帖数: 2483 | 20 一直认为面试出这么难得题真是过分啊！！
================= kth element in young tablet (M+N)log(numeric range)
solution ===========
const int M = 4;
const int N = 4;
int getOrder(int A[M][N], int tg)
{
int c = 0;
int i = 0;
int j = N-1;
while (i < M && j >= 0)
{
if (A[i][j] >= tg)
j--;
else
{
c += j+1;
i++;
}
}
return c+1;
}
int getKthMin(int A[M][N], int k)
{
if (k <= 0 || k > M*N)
return INT_MIN;
int nBe... 阅读全帖 |
|
l**h
发帖数: 893 | 21 老题了，还是不知道怎么找？
Find kth smallest element from an unsorted array in linear time. worst case
complexity should be O(n+k)
where n is array size. |
|
u*****o
发帖数: 1224 | 22 这个就是找kth prime number的算法啊。。二爷咋会不知呢，又逗我这个傻姑娘了。。
。 |
|
u*****o
发帖数: 1224 | 23 好的，放到1楼了，的确不是找kth prime的，而是找1-N之间的所有素数。。囧 |
|
u*****o
发帖数: 1224 | 24 是我没说清。。这题是找2-N之间的素数，不是找KTH PRIME的。。如果要找，是不是得
加个counter |
|
C*******n
发帖数: 24 | 25 Find the Kth smallest element in 2 sorted
array. so if you have 2 arrays&#
160;[1, 5, 9, 15, 20, 34] and [2, 6,
8, 10, 11, 19] and k = 5, the&
#160;answer is 8. Basically whats the
5th smallest number in the 2 arrays
combined.
Any ideas? |
|
r****c
发帖数: 2585 | 26 kth smallest is O(log(k))
medium is m+n/2 so it is O(log(m+n)). Notice O(log M + logN) is the same as
O(log (M+N)) so no difference. |
|
l******a
发帖数: 14 | 27 Here is another try:
Sp=0;
Ep=n-1;
While (sp
{
mid=(sp ep)/2;
Pick m[mid][mid],
walk up and right to find last column index on each row( above row mid) that
is less than m[mid][mid]
Then walk down and left to find last column index on each row( below row mid
) that is less than m[mid][mid]
Now you have separate the whole data set to 2 data set in 2n time
If first set count>k, ep=mid;
Else{ sp= mid 1;k-=count of set 1;}
}
So loop logn time! you will find the final mid associate with 2n elemen... 阅读全帖 |
|
s********k
发帖数: 2352 | 28 kth element难道不是matrix[k/n][k%n-1]？ |
|
|
l******a
发帖数: 14 | 30 Here is another try:
Sp=0;
Ep=n-1;
While (sp
{
mid=(sp ep)/2;
Pick m[mid][mid],
walk up and right to find last column index on each row( above row mid) that
is less than m[mid][mid]
Then walk down and left to find last column index on each row( below row mid
) that is less than m[mid][mid]
Now you have separate the whole data set to 2 data set in 2n time
If first set count>k, ep=mid;
Else{ sp= mid 1;k-=count of set 1;}
}
So loop logn time! you will find the final mid associate with 2n elemen... 阅读全帖 |
|
s********k
发帖数: 2352 | 31 kth element难道不是matrix[k/n][k%n-1]？ |
|
|
a********r
发帖数: 217 | 33 假设BST每个key都是 >=0 的整数，而且不重复，有没有时间复杂度是O(lgn)的算法来
search kth smallest key. inorder traversal似乎不能满足要求。 |
|
l*********b
发帖数: 65 | 34 我在想能不能通过level order的遍历 然后数数 大概判断一下kth在左还是在右 这样
大概就是logN了 但是仔细想了半天 思路不通。。。 而且恐怕事先不知道有多少个
node且bst不是balanced
。。。个人觉得 可能就还是线性时间复杂度吧- - |
|
|
|
|
o******8
发帖数: 620 | 38 欧洲的老大们好。
六月上旬要去瑞典 Stockholm 的 KTH，他们负责找的住处据说要转地铁，请问在学校
附近有没有
步行可以到的sublet? 14,15天，有信息的朋友请和我联系一下。
没去过欧洲，老大们有什么建议没有？Stockholm有什么好玩的，风景，人文，安全注
意事项？
多谢！！！ |
|
i***n
发帖数: 216 | 39 老板说他认识KTH的人， 说哪里signal processing 不错. 我从来么有听说过这个学校
。。。
知道的大侠可以告诉我一些信息么？ |
|
|
W*****e
发帖数: 7759 | 41 KTH is a decent institute and Signal Processing is strong. Most of the
graduates end up working for Ericsson or academia, and two graduates joined
McKinsey. Please check the webpages for Prof. Ottersten and other professors. |
|
c*********t
发帖数: 2921 | 42 常常看到以下说法，就是不知道到底指的是什么？
a. kth largest number
b. kth smallest number
c. kth to last element
d. kth to firt element
对于问题a，b ，有个例子如果有一个数组，数组的size 是100，里面的值是1-100的自
然数，
就是说里面的数有 （不一定是排序的）1, 2， 3， ............., 100
对于问题a:
kth largest number 是多少？是100-k? 还是100-k+1?, 俺的理解是100是largest
number, 99 是第二大的数，98 是第三大的数。100=100-1+1， 99=100-2+1， 98=100-
3+1.
我的理解对吗？
对于问题b:
kth smallest number 是多少？是k? 还是k+1?, 俺的理解是1是smallest number, 2
是第二小的数，3是第三小的数。
我的理解对吗？
对于问题a,b, k可以是0吗？我指的是可以有0th largest number 或者是0th smalle... 阅读全帖 |
|
c*********t
发帖数: 2921 | 43 【 以下文字转载自 JobHunting 讨论区 】
发信人: cookiesweet (apple), 信区: JobHunting
标 题: 弱弱的问问常出现的让俺糊涂的关于顺序的表述（有包子送）！！！
发信站: BBS 未名空间站 (Tue Sep 27 04:16:59 2011, 美东)
常常看到以下说法，就是不知道到底指的是什么？
a. kth largest number
b. kth smallest number
c. kth to last element
d. kth to firt element
对于问题a，b ，有个例子如果有一个数组，数组的size 是100，里面的值是1-100的自
然数，
就是说里面的数有 （不一定是排序的）1, 2， 3， ............., 100
对于问题a:
kth largest number 是多少？是100-k? 还是100-k+1?, 俺的理解是100是largest
number, 99 是第二大的数，98 是第三大的数。100=100-1+1， 99=100-2+1， 98=100-
3+1.
我的理解对... 阅读全帖 |
|
a***a
发帖数: 739 | 44 两个排序的数组A, B, 比如：
int[] A = { 0, 4, 7};
int[] B = { 2, 3, 8, 10};
寻找两个数组合起来kth最大的，比如
findKthLargest(A, B, 1) return 10
findKthLargest(A, B, 3) return 7
http://www.glassdoor.com/Interview/Take-two-sorted-arrays-and-f
大家看看我的方法对不对。
public static int findKthLargest(int[] A, int[] B, int k){
int startA=Math.max(0,A.length-k), startB=Math.max(0, B.length-k);
int endA=A.length-1, endB=B.length-1;
while (startA<=endA && startB<=endB){
int midA = (startA+endA)/2;
int midB = (st... 阅读全帖 |
|
s*x
发帖数: 8041 | 45 找到这个了：
1984 年的时候，UNIX 创造者之一 Ken Thompson 获得了 ACM 图灵奖。他的获奖演讲
叫做 Reflections on Trusting Trust（反思对信任的信任）。
在这个稿子只有三页纸的演讲中他分三步描述了如何构造一个非常难以被发现的编译器
后门。这后来被称为 the Ken Thompson Hack（KTH），有人说它是 the root
password of all evil。
在第一步里，Thompson 展示了一个可以输出自己的源代码的 C 程序。这需要一定技巧
，但很多人作为编程练习都做过。
在第二步里，Thompson 在 C 的编译器里增加了一段代码（后门），让它在检测到自己
在编译 UNIX 的 login 命令时在输出里插入一个后门。这个后门会允许作者用特定密
码以 root 身份登录系统。
在第三步里，Thompson 在第二步的编译器里使用第一步的方法加入另一段代码（后门
生成器），使得这个编译器在检测到它在编译自己时自动把第二步的后门和第三步的后
门生成器插入到输出里。
在得到一个第三步的编译器后，就可以把第二、三... 阅读全帖 |
|
l*****a
发帖数: 14598 | 46 I am confused of the explaination
=============================================
Direct application of the quick sort based selection algorithm
The quick sort based selection algorithm can be used to find k smallest or
k largest elements. To find k smallest elements find the kth smallest
element using the median of medians quick sort based algorithm. After the
partition that finds the kth smallest element, all the elements smaller
than the kth smaller element will be present left to the kth eleme |
|
f********y
发帖数: 20 | 47 全部
hujun
0楼 05月18日 06:15占着茅坑不拉屎, 利用学校资源为自己创造财富, 腰间别着中
组部的许可证大挣纳税人的钱.
bookface
1楼 05月17日 01:13当年评上教授，qiumin究竟里面做了多少科研的工作，走了什
么样的捷径，想必他自己心里清楚。此君一来，就试图贴上某位国家领导同志，速度真
是快。中国不愧为政治大国，只要搞搞政治，就能包治百病。
bookface
2楼 05月17日 01:11与qiumin先生在KTH有过一面之缘。在KTH，qiumin教授就很能
搞小动作，故和那边有几个教授关系不是很好。Qiumin教授在瑞典以少数裔人群成功人
士的形象经常在电视上露面，接受采访，确实，这样收效显著，扩大自己的知名度，也
间接带来了申请项目的机会。但是像瑞典这种多元的国家，教授也仅仅是教授而已。
bookface
3楼 05月17日 01:11与qiumin先生在KTH有过一面之缘。在KTH，qiumin教授就很能
搞小动作，故和那边有几个教授关系不是很好。Qiumin教授在瑞典以少数裔人群成功人
士的形象经常在电视上露面... 阅读全帖 |
|
f********y
发帖数: 20 | 48 全部
hujun
0楼 05月18日 06:15占着茅坑不拉屎, 利用学校资源为自己创造财富, 腰间别着中
组部的许可证大挣纳税人的钱.
bookface
1楼 05月17日 01:13当年评上教授，qiumin究竟里面做了多少科研的工作，走了什
么样的捷径，想必他自己心里清楚。此君一来，就试图贴上某位国家领导同志，速度真
是快。中国不愧为政治大国，只要搞搞政治，就能包治百病。
bookface
2楼 05月17日 01:11与qiumin先生在KTH有过一面之缘。在KTH，qiumin教授就很能
搞小动作，故和那边有几个教授关系不是很好。Qiumin教授在瑞典以少数裔人群成功人
士的形象经常在电视上露面，接受采访，确实，这样收效显著，扩大自己的知名度，也
间接带来了申请项目的机会。但是像瑞典这种多元的国家，教授也仅仅是教授而已。
bookface
3楼 05月17日 01:11与qiumin先生在KTH有过一面之缘。在KTH，qiumin教授就很能
搞小动作，故和那边有几个教授关系不是很好。Qiumin教授在瑞典以少数裔人群成功人
士的形象经常在电视上露面... 阅读全帖 |
|
L***s
发帖数: 9258 | 49 【 以下文字转载自 Returnee 讨论区 】
发信人: liujiatian (liujiatian), 信区: Returnee
标 题: 公示第十二批国家“千人计划” 青年人才名单的公告 (转载)
发信站: BBS 未名空间站 (Wed Dec 30 00:17:36 2015, 美东)
发信人: liujiatian (liujiatian), 信区: Biology
标 题: 公示第十二批国家“千人计划” 青年人才名单的公告
发信站: BBS 未名空间站 (Wed Dec 30 00:17:09 2015, 美东)
第十二批国家“千人计划”青年人才公示名单
序号 姓名 性别 出生日期 申报单位 落地省份 回国前任职单位
1 刘 毅 男 12/24/83 北京大学 北京 [美国]加州理工学院
[美国]California Institute of Technology
2 余 君 男 8/2/82 北京大学 北京 [美国]麻省理工学院
[美国]Massachuset... 阅读全帖 |
|
