多出的数字

发表于 | 更新于 | 分类于

多出的数字

Question

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

分析

使用二分法求解，计算复杂度为O(logn)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def search_extra_num(list_a, list_b, extra_index=0):
    index = len(list_b)//2
    if len(list_b) == 0:
        return extra_index
    if list_a[index] == list_b[index]:
        list_a = list_a[index+1:]
        list_b = list_b[index+1:]
        extra_index += search_extra_num(list_a, list_b, extra_index)+(index+1)
    else:
        if list_a[index]!= list_b[index-1]:
            return  index
        list_a = list_a[:index]
        list_b = list_b[:index]
        extra_index += search_extra_num(list_a, list_b, extra_index)
    return extra_index

list_a = [1,3,4,5,7,9,11,13,15,17,19]
list_b = [1,3,5,7,9,11,13,15,17,19]
index = search_extra_num(list_a, list_b)
print("多出数字的下标为：", index)
print("多出数字的数值为：", list_a[index])
多出数字的下标为： 2
多出数字的数值为： 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def search_extra_num1(list_a, list_b):
    assert len(list_a) == len(list_b)+1
    start = mid = 0
    end = len(list_b)
    while start < end:
        mid = (start + end)//2
        if mid == start:
            break
        if list_a[mid] == list_b[mid]:
            start = mid + 1
        else:
            if list_a[mid]!= list_b[mid-1]:
                break
            end = mid
    if list_a[mid] == list_b[mid]:
        mid = len(list_a) - 1
    return mid

list_a = [1,3,5,7,9,10, 11,13,15,17,19]
list_b = [1,3,5,7,9,11,13,15,17,19]
index = search_extra_num1(list_a, list_b)
print("多出数字的下标为：", index)
print("多出数字的数值为：", list_a[index])
多出数字的下标为： 5
多出数字的数值为： 10

1
2