442.FindAllDuplicatesinanArray-创新互联
https://leetcode.com/problems/find-all-duplicates-in-an-array/
新闻名称:442.FindAllDuplicatesinanArray-创新互联
转载注明:http://myzitong.com/article/deehjo.html
一列数,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://myzitong.com/article/deehjo.html