建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
首先想到的方法就是使用哈希表來(lái)記錄每個(gè)數(shù)字出現(xiàn)的次數(shù)。但是這種方法需要額外空間。在訪問(wèn)它之前將下標(biāo)為|x|-1上的數(shù)字取相反數(shù)。
十載的礦區(qū)網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都全網(wǎng)營(yíng)銷(xiāo)推廣的優(yōu)勢(shì)是能夠根據(jù)用戶(hù)設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整礦區(qū)建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)從事“礦區(qū)網(wǎng)站設(shè)計(jì)”,“礦區(qū)網(wǎng)站推廣”以來(lái)，每個(gè)客戶(hù)項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。
近來(lái)，我一直在刷leetcode，發(fā)現(xiàn)這個(gè)平臺(tái)真是一個(gè)好東西。它不僅可以幫助我們提高算法水平，而且還能鍛鍊我們的耐心和毅力。
今天要介紹的題目是“442. 數(shù)組中重復(fù)的數(shù)據(jù)”。這道題目給定了一個(gè)整數(shù)數(shù)組nums，其中有些元素出現(xiàn)兩次而其他元素只出現(xiàn)一次。找到所有在nums中出現(xiàn)兩次的元素。
首先想到的方法就是使用哈希表來(lái)記錄每個(gè)數(shù)字出現(xiàn)的次數(shù)。但是這種方法需要額外空間，并且時(shí)間復(fù)雜度為O(n)。如果要達(dá)到更優(yōu)秀的解決方案，則需要考慮原地修改數(shù)組。
那么如何原地修改呢？其實(shí)很簡(jiǎn)單，對(duì)于任意一個(gè)數(shù)字x，在訪問(wèn)它之前將下標(biāo)為|x|-1上的數(shù)字取相反數(shù)。如果已經(jīng)訪問(wèn)過(guò)該數(shù)字，則此時(shí)|x|必然小于等于n（n為數(shù)組長(zhǎng)度），因此我們可以根據(jù)abs(nums[i])-1是否小于n來(lái)判斷nums[abs(nums[i])-1]是否已經(jīng)被訪問(wèn)過(guò)。
具體實(shí)現(xiàn)見(jiàn)代碼：
```python
class Solution:def findDuplicates(self, nums: List[int]) -> List[int]:
res = []
for i in range(len(nums)):
if nums[abs(nums[i])-1]< 0:
res.append(abs(nums[i]))
else:
nums[abs(nums[i])-1] *= -1
return res
```
這里需要注意的是，我們要返回的是出現(xiàn)兩次的元素，而不是重復(fù)元素。因此如果一個(gè)數(shù)字已經(jīng)被訪問(wèn)過(guò)了，則它在數(shù)組中一定出現(xiàn)了兩次。
本文題目：每日l(shuí)eetcode：找出數(shù)組中的重復(fù)數(shù)據(jù)
新聞來(lái)源：http://www.5511xx.com/article/dhpccos.html
