一起來刷《劍指Offer》——不修改數組找出重複的數字（思路及Python實現）
- 2019 年 11 月 2 日
- 筆記
數組中重複的數字
在上一篇部落格中《劍指Offer》– 題目一：找出數組中重複的數字（Python多種方法實現）中，其實能發現這類題目的關鍵就是一邊遍曆數組一邊查滿足條件的元素。
然後我們在部落格用最複雜的方式學會數組（Python實現動態數組）這篇部落格中介紹了數組這一結構的本質，並自己動手實現了一個動態數組。
今天我們介紹一下另一道來自《劍指Offer》的關於數組的面試題——不修改數組找出重複的數字。
不修改數組找出重複的數字
題目二：不修改數組找出重複的數字
給定一個長度為 n+1 的數組裡的所有數字都在 0∼n 的範圍內，所以數組中至少有一個數字是重複的。
請找出數組中任意一個重複的數字，但不能修改輸入的數組。
樣例：
給定長度為8的數組 nums = [2， 3， 5， 4，3， 2， 6，7]
那麼輸出重複的數字2或者3
思路
首先我們得關注到，題目要求是：不修改數組，然後還是 返回任意一個重複的數字 。所以解題思路相比而言變少了：
-
哈希表：跟上一題一樣，本題也可以創建一個哈希表，如果原數組的每個數字第一次出現，就把他放到哈希表中去，即原數組大小為m的數字應該放到哈希表下標為m的位置上。空間複雜度是 (O(n)) 。
-
二分法：那麼有沒有不用空間複雜度(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))結果
思路一測試結果: 3 思路二測試結果: 3總結
其實，這種演算法不能保證找出所有重複的數字，比如不能找出[2, 3, 5, 4, 3, 2, 6, 7]重複數字2。
