leetcode287-- Find the Duplicate Number

leetcode287-- Find the Duplicate Number

题目

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

    You must not modify the array (assume the array is read only).
    You must use only constant, O(1) extra space.
    Your runtime complexity should be less than O(n2).
    There is only one duplicate number in the array, but it could be repeated more than once.

这个题目的意思是有一个长为n+1的数组,但是里面放的是1到n的数字,其中有一个是重复的,现在要把这个重复的给找出来,要求O(n)的时间,O(1)的空间.

如果不用python的一些很方便的包的话,我先是这样想的,


class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        flag = [False] * (len(nums)+1)
        
        for i in range(len(nums)):
            if not flag[nums[i]-1]:
                flag[nums[i]-1] = True
            else:
                return nums[i]

即用数组里面的数作为index,然后flag是记录这个数字有没有出现的,如果之前没有出现,说明这是第一次出现,就把他标记为True, 如果之前出现了就直接返回

但是这样用了O(n)的空间,不太好,

现在想想这个数组里面其实只有两个数字是一样的,其他的都是不一样的。

在网上看了别人这样写的,但是不太明白是为什么

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
            
        for i in range(len(nums)):
            if nums[abs(nums[i])]<0:
                return abs(nums[i])
            
            nums[abs(nums[i])] *= -1


也有这样弄的


class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
            
        for i in range(len(nums)):
            temp = nums[nums[0]]
            if temp < 0:
                return nums[0]
            else:
                nums[nums[0]] = -1
                nums[0] = temp
                

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦