找出數組中重複的數字

找出數組中重複的數字

找出數組中重複的數字


資料來源: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)。

One thought on “找出數組中重複的數字

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *