【Google】给两个已序数组，写一个函数求出第K小的数

双指针解法

two pointers

    public static int KthMin(int[] a,int[] b,int k){
        if(k > a.length+b.length){
            return -1; // no found case
        }
        int p1 = -1;
        int p2 = -1;
        while(p1 + 1 < a.length && p2 + 1 < b.length && k-->0){
            if(a[p1+1] <= b[p2+1]){
                p1++;
            }else{
                p2++;
            }
        }
        while(k-- >0){
            if(p1 + 1 < a.length ){
                p1++;
            }else{
                p2++;
            }
        }

        if(p1 < 0){
            return b[p2];
        }else if(p2 < 0){
            return a[p1];
        }else{
            return Math.max(a[p1],b[p2]);
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

扫线法

sweep line　two pointers

    public static int KthMin2(int[] a,int[] b,int k){
        if(k > a.length+b.length){
            return -1; // no found case
        }
        // 确定k在2个数组中的位置
        int p1,p2;
        if(a.length >= k){
            p1 = k - 1;
            p2 = -1;
        }else if(b.length >= k){
            p2 = k - 1;
            p1 = -1;
        }else{
            p1 = a.length-1;
            p2 = k - a.length - 1;
        }
        // 当p1或p2 小于 0，只需要单向扫
        if(p1 < 0){
            while(a[p1+1] < b[p2]){
                p1 ++;
                p2 --;
            }
        }else if(p2 < 0){
            while(b[p2+1] < a[p1]){
                p1 --;
                p2 ++;
            }
        }else{
        	// 下面2个while 最多只执行一个
            while(p1+1 < b.length && p2 >=0 &&  a[p1+1] < b[p2]){
                p1 ++;
                p2 --;
            }
            while(p2+1 < b.length && p1 >=0 &&  b[p2+1] < a[p1]){
                p1 --;
                p2 ++;
            }
        }
        // p1 或 p2出界，则说明第K小在另一个数组上
        if(p1 < 0 || p1 > a.length){
            return b[p2];
        }else if(p2 < 0 || p2>b.length){
            return a[p1];
        }else{
        　　// p1 p2未出界，取二者最大值，同上算法
            return Math.max(a[p1],b[p2]);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

TestCases

public static void main(String[] args) {
        // 1 2 2 3 3 5 5 7 7 8
        int[] a = new int[]{1,2,3,5,7,8};
        int[] b = new int[]{2,3,5,7};
        int[] expected = new int[]{1,2,2,3,3,5,5,7,7,8};
        for(int i=1; i<= 10; i++){
            assertEquals(KthMin(a,b,i),expected[i-1]);
        }
        for(int i=1; i<= 10; i++){
            assertEquals(KthMin2(a,b,i),expected[i-1]);
        }
    }
    private static void assertEquals(int a, int b){
        if(a != b){
            throw new RuntimeException(String.format("%d is not equals to %d",a,b));
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17