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

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

一、题目描述：

找出数组中重复的数字。

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

示例 1：

输入：

[2, 3, 1, 0, 2, 5, 3]

输出：2 或 3

限制：

2 <= n <= 100000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

这部分可以写写：

1. 这道题考察了什么思想？你的思路是什么？

   思路很简单啊，我们只需要遍历一遍数组，然后遇到重复的数字就结束遍历返回结果。我们需要使用集合来存放遍历时出现的数字，如果遍历时发现数字已经出现在集合中，则这个数字是重复数字。

2. 有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？

   

   

   

   class Solution {public int findRepeatNumber(int[] nums) {int i = 0;while(i < nums.length) {if(nums[i] == i) {i++;continue;}if(nums[nums[i]] == nums[i]) return nums[i];int tmp = nums[i];nums[i] = nums[tmp];nums[tmp] = tmp;}return -1;}
   }作者：jyd
   链接：https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/mian-shi-ti-03-shu-zu-zhong-zhong-fu-de-shu-zi-yua/
   来源：力扣（LeetCode）
   著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
   

三、AC 代码：

class Solution:def findRepeatNumber(self, nums: [int]) -> int:myset = set()for num in nums:if num in myset: return nummyset.add(num)return -1

四、总结：

如果你还有更多的思考、分析、总结，通通都加上来吧~

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

原地交换貌似也能这样写：

    for(int i = 0;i<nums.length;i++){while(nums[i]!=i){if(nums[i]==nums[nums[i]]){return nums[i];}    int temp = nums[nums[i]];nums[nums[i]]=nums[i];nums[i]=temp;       }}return -1;