剑指offer 03.数组中重复的数字解法

剑指offer 03.数组中重复的数字

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

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
今天做了这道题发现在pycharm上运行出来了，但提交后却超时，后来才知道这里有时间复杂度要求。

这道题描述为简单题，但其实不简单，后来借鉴了评论区的方法，我觉得非常好，这里分享出来python解法：

class Solution(object):
    def findRepeatNumber(self, nums):
         nums.sort()#先进行排序
         pre = nums[0]#令pre为nums下标为0位置的元素
         n = len(nums)#n为nums长度
         for index in range(1,n):
            if pre == nums[index]:
                return pre
            pre = nums[index]

这里减少了时间河空间复杂度在于，他先排序了，一但找到相同元素，会立刻得到返回值。遍历情况下可以减少时间。
这是我之前的代码，双重遍历，加判断。

class Solution(object):
    def findRepeatNumber(self, nums):
         for i in range(len(nums)):
             for j in range(len(nums)):
                 if i != j and nums[i]==nums[j]:
                    return nums[i]

后来经过改进的代码，用了集合去重。

class Solution(object):
     def findRepeatNumber(self, nums):
         Set = set(nums)
         for i in Set:
            if nums.count(i)>1:
                return i

减少了循环，但还时超出了时间。

大家好，我是一名普通大二在读双非本科生，大一处于整天沉迷游戏，混日子，后面发现大学还是要好好学习的。写博客完全是为了记录自己的学习，提升自己。