Jianbo Dai's

jz003.数组中重复的数字

 
  • Apr 29, 2020

数组中重复的数字

加一个系列，剑指offer里的题，比较容易想到的就是将数组遍历一遍然后用一个哈希表在O（1）复杂度内检查有无重复的数字，有则返回，时间复杂度为 O（n），但是这种方法提高效率是以一个大小为O（n）的哈希表为代价的。第二种常见的算法是将数组排序，再扫描一遍从其中找出重复数字，比较简单， 时间复杂度(因为排序)为O（nlogn）。第三种方法比较经典，其思路是，从头开始遍历数组，检查第i个数的值与i是否相等，若相等则继续，若不想等，则 将第i个数字与第第i个数字所指的值的数比较，若相同，则返回值，若不同，则继续该步骤直至找到重复数字或满足第一个条件（即第i个数的值与i相等）, 虽然代码中有两重循环，但对每个数来说最多只需两次即可找到自己的位置，所以该算法的时间复杂度为O（n）。并且操作都在原先数组上进行，空间复杂度 为O（1）。

class Solution:
    def findRepeatNumber1(self, nums: List[int]) -> int:
        hashtable = {}
        for i in nums:
            if i in hashtable:
                hashtable[i] += 1
                return i
            else:
                hashtable[i] = 1

    def findRepeatNumber2(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                return nums[i]

    def findRepeatNumber3(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            while nums[i] != i:
                if nums[i] == nums[nums[i]]:
                    return nums[i]
                else:
                    tmp = nums[i]
                    nums[nums[i]] = tmp
                    nums[i] = nums[nums[i]]
Search