找出數組中重複的數字

資料來源:https://mp.weixin.qq.com/s?__biz=MzI2NjI5MzU2Nw==&mid=2247488303&idx=2&sn=f8bc429f7fdcfdfdb181e378f5cf7395&chksm=ea910b7fdde68269c58171ab786444be6d09c5806ea1c80ed9852d9e5fdbd3f5f2ed12f8387d&scene=126&sessionid=1596416309&key=360754e56e03331926e8ed2b623edcd6223df98642be5bf0d4417ed1c1ec1c0d14a4779897482087fd8dc872b4d413c16c648c2f6016b6523f2cc7581d0dcc25a1b69ace3051660dff06c15df1e26352&ascene=1&uin=MjIwODk2NDgxNw%3D%3D&devicetype=Windows+10+x64&version=62090529&lang=zh_TW&exportkey=AoTd0VbzGmoSpdCqFc%2Fi7is%3D&pass_ticket=cKTjH2fY%2BPp0i6xoKXTuA6grSXna%2Fe2CKu8JbgWhPZjAQZuzdYgIvkBj%2BsDBxT9n

題目描述

    在一個長度為n的數組裡的所有數字都在0到n-1的範圍內。數組中某些數字是重複的，但不知道有幾個數字重複了，也不知道每個數字重複了幾次。請找出數組中任意一個重複的數字。例如，如果輸入長度為7的數組{2, 3, 1, 0, 2, 5, 3}，那麼對應的輸出是重複的數字2或者3。

解法一

    排序後，順序掃描，判斷是否有重複，時間複雜度為O(n²)。

解法二

    利用哈希表(雜湊表 – Hash table），遍歷數組，如果哈希表中沒有該元素，則存入哈希表中，否則返回重複的元素。時間複雜度為O(n)，空間複雜度為O(n)。