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