有人知道奕尚网吗？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Fashion - 美丽时尚

有人知道奕尚网吗？

有人知道奕尚网吗？# Fashion - 美丽时尚

C*n2010-10-11 07:10

1 楼

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?

o*n2010-10-11 07:10

2 楼

100天，打了个盹，就让姥姥弄成这样了

b*j2010-10-11 07:10

3 楼

有没有人在那里买过东西？(sasacity.com in china)

e*g2010-10-11 07:10

4 楼

sorted
6,
the&
假设数组是A[n], B[m], n > m
if k > m + n return -1
else 对A[1:min(k,n)] 和 B[1:min(k,m)] 递归二分查找

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

: 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?

n*f2010-10-11 07:10

5 楼

O(Logn logm),最优解法，leetcode上有。
给A一个指针i，给B一个指针j。binary search，i,j初识化为k/2吧，如果，越界，适
当调整。比如其中一个取数组上限m，另一个取k-m。
如果A[i]else if A[i]k, j= (j j-(i j-1))/2;
Else if A[i] >= B[j] and i j<=k, j=(j j-(j i-k-1))/2;
Else i = (i i-(i j-k-1)/2);
Repeat this process until i and j keep stable;
If (i j = k) return max(A[i], B[j]);
Else return min(A[i], B[j]);
Ipad打字真累，求轻拍。
一句话，就是找到两个数组的一个指针，使左边个数和等于k。

n*f2010-10-11 07:10

6 楼

o(logm logn)

n*f2010-10-11 07:10

7 楼

加号打不出来。。。

k*62010-10-11 07:10

8 楼

请问是leetcode上哪道题呀？

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

: O(Logn logm),最优解法，leetcode上有。
: 给A一个指针i，给B一个指针j。binary search，i,j初识化为k/2吧，如果，越界，适
: 当调整。比如其中一个取数组上限m，另一个取k-m。
: 如果A[i]: else if A[i]k, j= (j j-(i j-1))/2;
: Else if A[i] >= B[j] and i j<=k, j=(j j-(j i-k-1))/2;
: Else i = (i i-(i j-k-1)/2);
: Repeat this process until i and j keep stable;
: If (i j = k) return max(A[i], B[j]);
: Else return min(A[i], B[j]);