442.FindAllDuplicatesinanArray-創(chuàng)新互聯(lián)

https://leetcode.com/problems/find-all-duplicates-in-an-array/442.FindAllDupli catesinanArray

一列數(shù)，1 ≤ a[i] ≤ n (n = size of array)，有的出現(xiàn)一次有的出現(xiàn)兩次，輸出出現(xiàn)兩次的數(shù)。

重慶網(wǎng)站制作公司哪家好，找成都創(chuàng)新互聯(lián)！從網(wǎng)頁設計、網(wǎng)站建設、微信開發(fā)、APP開發(fā)、成都響應式網(wǎng)站建設公司等網(wǎng)站項目制作，到程序開發(fā)，運營維護。成都創(chuàng)新互聯(lián)公司2013年成立到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗和運維經(jīng)驗，來保證我們的工作的順利進行。專注于網(wǎng)站建設就選成都創(chuàng)新互聯(lián)。

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]


耿直的你大概會寫出如下代碼
class Solution(object):
def findDuplicates(self, nums):
        myset=set()
for x in nums:
if nums.count(x)==2:
                myset.add(x)
return list(myset)

這就是engineering和science的區(qū)別，在工程中可能要統(tǒng)計2，也有可能以后需求要變會統(tǒng)計100，這時候這個代碼改動就少

但是這可是LeetCode，在遍歷中用count（）妥妥會TLE，題目也說了Could you do it without extra space and in O(n) runtime?

這時候你就需要用到各種奇技淫巧了

注意到：

1、數(shù)組內(nèi)元素只會出現(xiàn)一次或兩次，沒有其他的情況。

2、所有元素都是正整數(shù)，且大于等于1

然后你突開腦洞，把數(shù)組遍歷，將nums[x-1]的數(shù)翻面變負，如果在遍歷中判斷的時候發(fā)現(xiàn)這個數(shù)已經(jīng)是負的了，說明出現(xiàn)了兩次

class Solution(object):
def findDuplicates(self, nums):
        res= []
for x in nums:
if nums[abs(x) - 1] < 0:
                res.append(abs(x))
else:
                nums[abs(x)- 1] *= -1
   return res

什么？覺得有點看不懂？來個簡單易懂的，也能過

class Solution(object):
def findDuplicates(self, nums):
        res= []
for x in nums:
            nums[abs(x)- 1] *= -1
   for x in nums:
if nums[abs(x) - 1] > 0:
                res.append(abs(x))
return list(set(res))

分享名稱：442.FindAllDuplicatesinanArray-創(chuàng)新互聯(lián)
URL分享：http://muchs.cn/article20/deehjo.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、面包屑導航、外貿(mào)網(wǎng)站建設、動態(tài)網(wǎng)站、手機網(wǎng)站建設、云服務器

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

微信小程序開發(fā)