题目描述 剑指 Offer 03. 数组中重复的数字 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
来源：力扣（LeetCode）
""" 三种解决方案 1. 排序 遇到第一个前后相同的元素 为重复元素。 时间复杂度 n*logn 2. 一遍遍历放入到 如果哈希表不存在该元素则放入到哈希表内，如果存在则return重复 时间复杂度 n 空间复杂度 n 3. 还是排序，通过该列表的特点 因为 n元素都是在 0 -n-1 范围之内 因此和下标对应。如果同一个下标放有多个该元素。时间复杂度n。 """ """ 问题 1：不会写 n*logn的排序算法 """ # 哈希查找 def findduplicateelement(n_list): if len(n_list): dict1 = {} for i in range(len(n_list)): if n_list[i] not in dict1: dict1[n_list[i]] =i else: return n_list[i] # 排序 """ 1. 判断当前元素 是否 和下标相等 如果不相等则 判断当前元素是否和 以当前元素为下标的元素是否相等，如果都不相等则交换。 """ def findduplicateelement1(nums): if len(nums): for i in range(len(nums)): while nums[i] != i: print(nums,i) if nums[i] != nums[nums[i]]: # 使用这句语法是错的 牵扯深拷贝 浅拷贝的问题 引用的问题。 #nums[i],nums[nums[i]] = nums[nums[i]],nums[i] temp = nums[nums[i]] nums[nums[i]] = nums[i] nums[i] = temp else: return nums[i] if __name__ == '__main__': """ 测试用例: 1. 存在 重复的 2. 不存在重复的 3.传入为空 """ n_list = [2, 3, 1, 0, 2, 5, 3] print(findduplicateelement1(n_list)) print(findduplicateelement(n_list))