題目
在一個(gè)長(zhǎng)度為n的數(shù)組里所有數(shù)字都是在0~n-1范圍內(nèi).數(shù)組中某些數(shù)字是重復(fù)的.但是不知道有幾個(gè)數(shù)字重復(fù)了.也不知道每個(gè)數(shù)字重復(fù)了幾次.請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字.如果有重復(fù)的,返回true.如果沒(méi)有.返回false
三種思路
- 排序,然后從頭到尾掃描,時(shí)間復(fù)雜度是O(nlogn)
- 哈希表
從頭到尾順序掃描每個(gè)元素,每掃描到一個(gè)數(shù)字,判斷這個(gè)哈希表里是否存在.如果沒(méi)有就加入,如果有就不加入.返回true.時(shí)間復(fù)雜度是O(n),但是需要額外的存儲(chǔ)空間O(n) - 時(shí)間復(fù)雜度O(n),空間復(fù)雜度是O(1)
從頭開(kāi)始掃描,如果當(dāng)前的i位置的元素并不是i.而是j.就把i和j互換位置,如果還不是就一直替換到第i個(gè)位置的元素為i位置
