未分类

多出的数字

编程题

问题：在两个输入的数组中除了一个数字之外其余数字的值和顺序都相同，第一个数组比第二个数组多一个数字。请问如何找出第一个数组中多出的数字的下标？例如如果输入两个数组{2, 4, 6, 8, 9, 10, 12}和{2, 4, 6, 8, 10, 12}，则输出4，该下标对应的数字是9。

方法一：对数组进行遍历比较

方法二：使用二分法

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
49
50
51
52
53
54
55
56
57
58
public class Test__ {

    public static void main(String[] args) {
        int a[] = {1, 2, 4, 6, 8, 10, 12};
        int b[] = {2, 4, 6, 8, 10, 12};

        System.out.println(findDifference(a, b));

    }


    public static int findDifference(int a[], int b[]) {
        int start, mid, end;
        //判断a，b数组是否符合要求
        if (a == null || b == null || a.length != b.length + 1)
            return -1;

        end = a.length - 1;
        start = 0;

        /**找出多出的数字，start的结果就是该数字的下标**/
        while (start <= end) {

            if (start == end)
                break;
            mid = (start + end) / 2;
            //由于mid的值是向下取整的结果，不会取到a.length - 1，所以不会出现越界的问题
            if (a[mid] == b[mid]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        //对于符合要求的情况，返回-1，可以设置一个全局变量，告诉调用者此结果是不合法时的情况
        //此外还需要加上验证结果的步骤，除去那个多出的值，要验证两个数组其余对应位置的值都相等
        /**对数组的合法性进行验证**/
        int i = 0, j = 0;
        for (i = 0; i < a.length && j < a.length; i++, j++) {
            if (i == start) {
                j--;
                continue;
            } else if (a[i] != b[j]) {
                System.out.println("数组不合法");
                break;
            }
        }
        //如果除了多出的那个数字，其余的都比较过，那么这个结果就是符合的
        if (i == a.length)
            return start;

        return -1;
    }

}
/**
 * 如有错误缺漏，请不吝赐教
 **/

题目来源：

程序员面试题精选100题(74)-多出的数字 - 算法

分享到