剑指offer（第2版）

移动开发2024-04-10 01:09:50

4/75

03.找出数组中重复的数字

try1: 遍历超时 $剑指offer（第2版）,O(n^2),第2张$

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)-1):
            for j in range(i+1,len(nums)): # 第一次写忘记+1了
                if nums[i] == nums[j]:
                    return nums[I]

try2: 字典 $剑指offer（第2版）,O(2n),第3张$

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        dic = {}
        for i in range(len(nums)):
            if nums[i] not in dic:
                dic[nums[i]] = 1
            else:  # 下面多余
                dic[nums[i]] += 1
        for i in dic.keys():
            if dic[i] > 1:
                return i # 第一次写错为了return dic[I]

try3:改进字典 $剑指offer（第2版）,O(n),第4张$

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        dic = {}
        for i in range(len(nums)):
            if nums[i] not in dic:
                dic[nums[i]] = 1
            else:
                return nums[I]