logo
Redian新闻
>未名空间
>pets - 心有所宠
>
多尔衮对小T 说：
avatar
多尔衮对小T 说：# pets - 心有所宠
c*g
1 楼
Question: Find the k-th Smallest Element in the Union of Two Sorted Arrays
Given two sorted arrays A, B of size m and n respectively. Find the k-th
smallest element in the union of A and B. You can assume that there are no
duplicate elements.
http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-u
如果A组划k/2，B组划k/2来比较。为方便解释，这里先假设k为偶数,并且m,n>k/2.
如果不满足这些条件，在计算index的时候，会考虑这些情况。
if A[k/2 - 1] == B[k/2 -1] done.
if A[k/2 - 1] > B[k/2 -1]
那么在A[k/2 + 1 - k] 和 B[0 k/2 - 1] 里取k/2 smallest number。
if A[k/2 - 1] < B[k/2 -1] in a similar way
所以是一个recursion问题。而且数组大小按照对半的速度下降。所以是O(lgk)
另外，如果k很大，超过(m+n)/2，我们可以求 (m+n - k + 1) largest number，以减
少计算时间。
这个速度比链接上讲的lgm + lgn好些吧。
avatar
x*y
2 楼
地里的刀豆只剩杆子了，咬口很干净俐落，番茄也是，哪怕是种高盆里的也被清空了，
干茎有被拉扯过的痕迹，看不出什么咬的好像这些果子从来就不曾长出来过。
会是啥呢？我们这里没鹿，只有野兔野猫，兔子会吃番茄？一晚上吃掉七八个大果的节
奏哎。
avatar
A*R
3 楼
小T,是爷们，要挺住！
avatar
d*a
4 楼
你不能确定m 或者n比k/2大，所以A[k/2 - 1]是很可能越界的访问。
avatar
t*a
5 楼
有照片么?
avatar
Q*A
6 楼
^0^这个表情很大义凛然！
avatar
c*g
7 楼
我这是为了阐述方便。
如果A组划k/2，B组划k/2来比较。为方便解释，这里先假设k为偶数,并且m,n>k/2.
如果不满足这些条件，在计算index的时候，会考虑这些情况。也不复杂.用
Math.max(A.length-1,k/2）

【在 d******a 的大作中提到】
: 你不能确定m 或者n比k/2大，所以A[k/2 - 1]是很可能越界的访问。
avatar
y*2
8 楼
很有可能是野兔干的，兔子吃西红柿，上chicken wire吧。

【在 x**y 的大作中提到】
: 地里的刀豆只剩杆子了，咬口很干净俐落，番茄也是，哪怕是种高盆里的也被清空了，
: 干茎有被拉扯过的痕迹，看不出什么咬的好像这些果子从来就不曾长出来过。
: 会是啥呢？我们这里没鹿，只有野兔野猫，兔子会吃番茄？一晚上吃掉七八个大果的节
: 奏哎。
avatar
A*R
9 楼
嗯，有点愣劲！

【在 Q****A 的大作中提到】
: ^0^这个表情很大义凛然！
avatar
c*g
10 楼
code is here. Please comment on this.
平时不用Java的，发现做题用Java比C++方便（没指针，有更多的函数，呵呵）
另外，函数返回一个boolean（有可能数组根本没有k这么多elements）和一个number。
查了网，说可以用一个临时类，来返回其对象。我嫌麻烦，用了一个输入变量来返回
number值。但是直接不能返回，所以用了int[]。觉得有点awkward。不知你们怎么处理？
package leetcode;
import java.util.*;
public class kthSmallestElementTwoSortedArrays_Ver2 {

public static void main(String[] str)
{
// build two sorted arrays:
int[] A = {1,3,4,4, 7,9,10, 13, 15, 19, 20, 33};
int[] B = {2,5,5,6,12 };

// int[] A = {1,3,4,4, 7,9,10, 13, 15, 19, 20, 33};
// int[] B = {2,5,5 };
int[] result = {0};
boolean TF = findKthSmallest(A,B,8,result);
System.out.println(TF + ", " + result[0]);

}

public static boolean findKthSmallest(int[] A, int[] B, int k, int[]
result)
{
boolean TF = findKthSmallest(A, 0, A.length-1,
B, 0, B.length-1, k, result);
return TF;
}

public static boolean findKthSmallest(int[] A, int A_l, int A_r,
int[] B, int B_l, int B_r, int k, int[] result)
{

if (A_r - A_l + 1 + B_r - B_l + 1 < k) return false;
if (A_r - A_l + 1 + B_r - B_l + 1 == k) {result[0] = Math.min(A[A_r
], B[B_r]); return true;}

if (k == 1)
{
if (A[A_l] < B[B_l])
{result[0] = A[A_l]; return true;}
else
{result[0] = B[B_l]; return true;}
}

if (A_l == A_r)
{
if (A[A_l] < B[B_l + k - 1 - 1])
{result[0] = B[B_l + k - 1 -1 -1 ]; return true;}
else
{result[0] = B[B_l + k - 1 -1 ]; return true;}
}
if (B_l == B_r)
{
if (B[B_l] < A[A_l + k - 1 - 1])
{result[0] = A[A_l + k - 1 -1 -1 ]; return true;}
else
{result[0] = A[A_l + k - 1 -1 ]; return true;}
}

int A_ind1, A_ind2, B_ind1, B_ind2;
if (A_r - A_l < B_r - B_l)
{
A_ind1 = A_l;
A_ind2 = Math.min(A_r, A_l + k/2 - 1 );


B_ind1 = B_l;
B_ind2 = B_l + (k - (A_ind2 - A_ind1 + 1)) - 1;
}
else
{
B_ind1 = B_l;
B_ind2 = Math.min(B_r, B_l + k/2 - 1 );


A_ind1 = A_l;
A_ind2 = A_l + (k - (B_ind2 - B_ind1 + 1)) - 1;
}


if (A[A_ind2] == B[B_ind2]) {result[0] = A[A_ind2]; return true;}
if (A[A_ind2] < B[B_ind2])
{
if (A_ind2 == A_r) {result[0] = B[B_ind2]; return true;}

int A_ind3 = Math.min(A_ind2+1, A_r);
int A_ind4 = Math.min(A_r, A_ind2 + (B_ind2 - B_ind1 + 1));

boolean TF = findKthSmallest(A, A_ind3, A_ind4,
B, B_ind1, B_ind2, (B_ind2 - B_ind1 + 1), result);

return TF;
}

if (A[A_ind2] > B[B_ind2])
{
if (B_ind2 == B_r) {result[0] = A[A_ind2]; return true;}

int B_ind3 = Math.min(B_ind2+1, B_r);
int B_ind4 = Math.min(B_r, B_ind2 + (A_ind2 - A_ind1 + 1));

boolean TF = findKthSmallest(A, A_ind1, A_ind2,
B, B_ind3, B_ind4, (A_ind2 - A_ind1 + 1), result);

return TF;
}

return false;
}

}
avatar
m*t
11 楼
肯定不是猫干的啦 猫吃不了很多的
avatar
m*u
12 楼
嗯，原来，做男人，也“挺”好。
ps.这表情跟我家包子真象阿，每次看到都忍不住给他揉上去。
avatar
l*c
13 楼
If the numbers of two sorted array are huge enough, can I write the code as
followed?
int returnKint(int* s1, int* s2, int start1, int start2, int k){
if (k == 1)
return s1[start1]else {
if (s1[start1+k/2-1] < s2[start2+k/2-1])
return returnKint(s1, s2, start1+k/2, start2, k-k/2);
else
return returnKint(s1, s2, start1, start2+k/2, k-k/2);
}
}
avatar
p*8
14 楼
今年气候不好，动物没有食物，祸害了好多苗
我的豇豆和扁豆有一半被齐根咬断
avatar
C*W
15 楼
赞多尔衮的脖子：）小T要加油呀~~~
avatar
c*g
16 楼
呵呵，of course. 前面我的code很多if语句是handle非常情况的。
比如A数字多，或者B数字多，等等。
不是说coding很注重考察边界条件吗？

as

【在 l****c 的大作中提到】
: If the numbers of two sorted array are huge enough, can I write the code as
: followed?
: int returnKint(int* s1, int* s2, int start1, int start2, int k){
: if (k == 1)
: return s1[start1]: else {
: if (s1[start1+k/2-1] < s2[start2+k/2-1])
: return returnKint(s1, s2, start1+k/2, start2, k-k/2);
: else
: return returnKint(s1, s2, start1, start2+k/2, k-k/2);
avatar
m*u
17 楼
我觉得是鹿干的
avatar
Q*A
18 楼
我觉得多多开始张围脖了，感觉脖子的毛像大围脖一样把整个头包住，只露出剩脸。

【在 A*********R 的大作中提到】
: 嗯，有点愣劲！
avatar
g*y
19 楼
贴个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[bi - 1]:
return alist[ai - 1]
elif alist[ai - 1] > blist[bi - 1]:
return findk(alist[:ai], blist[bi:], k - bi)
else:
return findk(alist[ai:], blist[:bi], k - ai)
avatar
o*i
20 楼
有点像鹿干的。兔子没那么大胃口。。。
avatar
P*o
21 楼
对眼很赞
有点像那个谁，明道？

【在 A*********R 的大作中提到】
: 小T,是爷们，要挺住！
avatar
c*g
22 楼
哈哈，good one.
你用了空阵列来对付exceptioanl cases，这样程序简单多了。
Java里没有空阵列，所以我用了很多if语句。但是在你python版的启发后，我可以定义
left,right indexes for assumed empty arrays。
Thanks!

【在 g****y 的大作中提到】
: 贴个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:
avatar
T*n
23 楼
兔子吃不了那么多西红柿吧，应该还有其他动物。
avatar
p*f
24 楼
京戏大吊眼。赞。
avatar
w*j
25 楼
嗯.
avatar
d*3
26 楼
我们家发生了一样的情况。我很清楚呢是水獭otter干的。那家伙横冲直撞的，跑到地
里摘了个青西红柿一屁股坐到那里就抱着啃起来了，这几天大点的西红柿给全吃光了。
有的菜花种到盆里，它够不到，就给搬倒。真是没办法了。这几天在想怎么把我们家的
fence修一下，将会是个很大的工程。哎。。。
avatar
A*R
27 楼
早就这样了，要不俺说长得越来越衰了 :(

【在 Q****A 的大作中提到】
: 我觉得多多开始张围脖了，感觉脖子的毛像大围脖一样把整个头包住，只露出剩脸。
avatar
x*0
28 楼
mark
avatar
x*y
29 楼
鹿我们这里没的，切口都在挺高位置的，至少2ft，而且有的在死角位置四周都是花盆
，也没花盆被翻的迹象，悬案了。
avatar
l*e
30 楼
斗鸡眼儿？
avatar
A*R
31 楼
咱两换猫吧

【在 m**u 的大作中提到】
: 嗯，原来，做男人，也“挺”好。
: ps.这表情跟我家包子真象阿，每次看到都忍不住给他揉上去。
avatar
A*R
32 楼
哪个？

【在 P******o 的大作中提到】
: 对眼很赞
: 有点像那个谁，明道？
avatar
A*R
33 楼
5555555

【在 l*****e 的大作中提到】
: 斗鸡眼儿？
avatar
m*u
34 楼
典型的ragdoll男猫长相，包子也是这么个大围脖，就是多多毛短一点点。

【在 A*********R 的大作中提到】
: 早就这样了，要不俺说长得越来越衰了 :(
avatar
A*R
35 楼
小T 是小狗，生命力强，恢复快，肯定没事的！

【在 C*****W 的大作中提到】
: 赞多尔衮的脖子：）小T要加油呀~~~
avatar
P*o
36 楼


【在 A*********R 的大作中提到】
: 哪个？
avatar
m*u
37 楼
只换蜜蜜。我已经受够臭小子了。不过，他爹肯定不能答应......

【在 A*********R 的大作中提到】
: 咱两换猫吧
avatar
A*R
38 楼
这个角度有点，平时看没有这明显

【在 p********f 的大作中提到】
: 京戏大吊眼。赞。
avatar
m*u
39 楼
这还是日本人？切，太奶油，多多比他有气势多了。

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

avatar
A*R
40 楼
俺用多多换这个。。。

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

avatar
P*o
41 楼
倒。。。我不看偶像剧的都知道他不是日本人。。。。

【在 m**u 的大作中提到】
: 这还是日本人？切，太奶油，多多比他有气势多了。
avatar
A*R
42 楼
那俺也换米线，就怕对大小姐伺候不周

【在 m**u 的大作中提到】
: 只换蜜蜜。我已经受够臭小子了。不过，他爹肯定不能答应......
avatar
Q*A
43 楼
因为太漂亮，我曾经一直以为多多是女娃。
现在还是漂亮！

【在 A*********R 的大作中提到】
: 早就这样了，要不俺说长得越来越衰了 :(
avatar
m*u
44 楼
我老古董了，不是10年前出道的都不认识。

【在 P******o 的大作中提到】
: 倒。。。我不看偶像剧的都知道他不是日本人。。。。
avatar
m*u
45 楼
米线走到哪儿，都得带着伺候的仆人，顺便搭着仆人的唠叨lg和坏脾气养子。没有身为
熟练工的猫奴，一般都伺候不了她。

【在 A*********R 的大作中提到】
: 那俺也换米线，就怕对大小姐伺候不周
avatar
l*e
46 楼

哈哈哈！！！！！！！

【在 A*********R 的大作中提到】
: 5555555
avatar
A*R
47 楼
难得你这样高看他

【在 m**u 的大作中提到】
: 这还是日本人？切，太奶油，多多比他有气势多了。
avatar
l*d
48 楼
哈哈，原来多多的全名是多尔衮呀，这名字牛！！

【在 A*********R 的大作中提到】
: 小T,是爷们，要挺住！
avatar
A*R
49 楼
谁叫人家长得美，猫奴伺候的心甘情愿，呵呵

【在 m**u 的大作中提到】
: 米线走到哪儿，都得带着伺候的仆人，顺便搭着仆人的唠叨lg和坏脾气养子。没有身为
: 熟练工的猫奴，一般都伺候不了她。
avatar
A*R
50 楼
多尔衮是他爹后来给取得，俺一直搅得多多啥，他爹叫得他有大智慧，窘

【在 l********d 的大作中提到】
: 哈哈，原来多多的全名是多尔衮呀，这名字牛！！
avatar
i*s
51 楼
re对眼。。。
另外。。。把明字儿看错了。。。 = =

【在 P******o 的大作中提到】
: 对眼很赞
: 有点像那个谁，明道？
avatar
M*a
52 楼
你家这咪太有喜感了，这背挺得，这眼对的 :P

【在 A*********R 的大作中提到】
: 小T,是爷们，要挺住！
avatar
A*R
53 楼
谢谢！就是脾气倔得像牛

【在 M*****a 的大作中提到】
: 你家这咪太有喜感了，这背挺得，这眼对的 :P
avatar
o*l
54 楼
这张很严肃
气场很大
爷们!

【在 A*********R 的大作中提到】
: 小T,是爷们，要挺住！
avatar
w*w
55 楼
這個眼神啊....
avatar
M*a
56 楼
ragdoll不是温顺的吗？多尔衮是叫兽还是母老虎？

【在 A*********R 的大作中提到】
: 谢谢！就是脾气倔得像牛
avatar
A*R
57 楼
叫兽，喜欢叫，性格总得还可以，就是倔

【在 M*****a 的大作中提到】
: ragdoll不是温顺的吗？多尔衮是叫兽还是母老虎？
avatar
p*y
58 楼
太好玩了。一起bless
avatar
m*s
59 楼
我咋怎么看怎么觉得你家猫长得像鹿鼎记里的敖拜呢?不叫多尔衮还想不到这个。

【在 A*********R 的大作中提到】
: 小T,是爷们，要挺住！
avatar
w*o
60 楼
多尔衮让我想到的是。。。马景涛。。。
avatar
A*R
61 楼
霸气有点像，多多刨猫沙能刨得沙土飞扬

【在 m****s 的大作中提到】
: 我咋怎么看怎么觉得你家猫长得像鹿鼎记里的敖拜呢?不叫多尔衮还想不到这个。
avatar
A*R
62 楼
可就没有马的艳福罗

【在 w***o 的大作中提到】
: 多尔衮让我想到的是。。。马景涛。。。
相关阅读
【征文】策论山寨君子六艺 (转载)大道和笨爹的粉很给力呀！【宝黛来了 】好吧，可爱风。。弱智儿童欢乐多（有点长）家里养鱼还能养猫吗？我家小咪闪奔日跟风~无预告闪奔~光速闪~~兮若娘之【重庆辣子鸡】 (转载)周六的下午请教大家这是什么狗狗？毕业典礼前一天破相了猫眼药再来个灰白对比小海豹找不到麻麻，最后哭了。。。被萌到了O>_<O (转载)刚才气死我了出门十天左右啊，两只猫咋办呢？Re: 萝莉咱萌的是蓝眼睛 (转载)战役升级今天到底有多少奔啊？不带这样的！！！我要飞了，舍不得猫猫~~
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。