442.FindAllDuplicatesinanArray-创新互联

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

一列数，1 ≤ a[i] ≤ n (n = size of array)，有的出现一次有的出现两次，输出出现两次的数。

重庆网站制作公司哪家好，找成都创新互联！从网页设计、网站建设、微信开发、APP开发、成都响应式网站建设公司等网站项目制作，到程序开发，运营维护。成都创新互联公司2013年成立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选成都创新互联。

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的区别，在工程中可能要统计2，也有可能以后需求要变会统计100，这时候这个代码改动就少

但是这可是LeetCode，在遍历中用count（）妥妥会TLE，题目也说了Could you do it without extra space and in O(n) runtime?

这时候你就需要用到各种奇技淫巧了

注意到：

1、数组内元素只会出现一次或两次，没有其他的情况。

2、所有元素都是正整数，且大于等于1

然后你突开脑洞，把数组遍历，将nums[x-1]的数翻面变负，如果在遍历中判断的时候发现这个数已经是负的了，说明出现了两次

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-创新互联
分享网址：http://bjjierui.cn/article/deehjo.html