资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

442.FindAllDuplicatesinanArray-创新互联

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

一列数,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://www.cdkjz.cn/article/deehjo.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220