Python面試不修改陣列找出重複的數位

2022-05-20 19:06:19

陣列中重複的數位

在上一篇部落格中劍指Offer之面試題3: 陣列中重複的數位中，其實能發現這類題目的關鍵就是一邊遍歷陣列一邊查滿足條件的元素。

然後我們在部落格用最複雜的方式學會陣列（Python實現動態陣列）這篇部落格中介紹了陣列這一結構的本質，並自己動手實現了一個動態陣列。

今天我們介紹一下另一道來自《劍指Offer》的關於陣列的面試題——不修改陣列找出重複的數位。

不修改陣列找出重複的數位

題目二：不修改陣列找出重複的數位

給定一個長度為 n+1 的陣列裡的所有數位都在 0∼n 的範圍內，所以陣列中至少有一個數位是重複的。

請找出陣列中任意一個重複的數位，但不能修改輸入的陣列。

樣例：

給定長度為8的陣列 nums = [2， 3， 5， 4，3， 2， 6，7]

那麼輸出重複的數位2或者3

思路

首先我們得關注到，題目要求是：不修改陣列，然後還是返回任意一個重複的數位。所以解題思路相比而言變少了：

1.雜湊表：跟上一題一樣，本題也可以建立一個雜湊表，如果原陣列的每個數位第一次出現，就把他放到雜湊表中去，即原陣列大小為m的數位應該放到雜湊表下標為m的位置上。空間複雜度是 $O(n)$ 。

2.二分法：那麼有沒有不用空間複雜度 $O(n)$ 的演演算法。假設沒有重複數，那麼1~n 之間，每個數都只能出現一次。而題目中，這個陣列至少有一個數位重複，即出現的次數大於1。

利用二分的思想：把 1~n 的數位從中間數位 m 開始分為兩部分，前一半為 1~ m，後面一半為 m+1 ~n，如果 1~m 中的數位在陣列中出現的次數大於 m，那麼這一半必定有重複的數位；

否則，那麼另一部分必定含有重複數位。接著我們，繼續對含有重複數位的區間一分為二，直到找到重複的數位。

思路一：雜湊表

def find_duplicated_num(nums):
    """hash_map"""
    hash_map = dict()
    for i, val in enumerate(nums):
        if val in hash_map:
            return val
        hash_map[val] = i
    return False

思路二：二分法

def reduce_inter(nums2, left, right):
    """ """
    mid = (left + right) // 2
    count = 0
    length = len(nums2)
    for i in range(length):
        if (nums2[i] >= left) and (nums2[i] <= mid):
            count += 1
    if count > mid - left + 1:
        return left, mid
    else:
        return mid+1, right


def find_duplicated_num2(nums2):
    left, right = 1, len(nums2) - 1
    while left != right:
        left, right = reduce_inter(nums2, left, right)
    return left

測試

nums = [2, 3, 5, 4, 3, 2, 6, 7]
# nums_n = [5, 4, 3, 2, 6, 7]
print("思路一測試結果: ", find_duplicated_num(nums))
print("思路二測試結果: ", find_duplicated_num2(nums))

結果