剑指Offer[03]-数组中重复的数字

题目

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例:

输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3 

python代码

class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # method 1
        # mid_hash = {}
        # for i in nums:
        #     if i in mid_hash:
        #         return i
        #     else:
        #         mid_hash[i] = 0

        # method 2
        nums.sort()
        pre = nums[0]
        for index in range(1, len(nums)):
            if pre == nums[index]:
                return pre
            pre = nums[index]

代码中给出了两种解法,两者在时间和空间上各有优势,我们逐一来分析。

  • 方法1 哈希法 时间复杂度:0(n),空间复杂度0(n)
    由于哈希表的特殊结构,使其在查找时效率很高,所以为了降低时间复杂度,我们可以使用哈希表来辅助查找。
    在暴力查找时,我们遍历每个元素,并使用in来判断是否存在重复元素(也就是这个操作比较耗时,在list中时间复杂度为O(n)),哈希法优化了in这一步,将list的元素作为字典的key,因为在字典中in的时间复杂度约为0(1)。

  • 方法2 排序法 时间复杂度:0(nlogn),空间复杂度0(1)
    这个思路比较直观,我直接将list排序,然后依次遍历,只要相邻的两个元素相等,则为重复

发表评论

电子邮件地址不会被公开。