找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
限制：
2 <= n <= 100000
思路：
利用计数排序，在统计次数的时候判断出现次数是否大于1，如果大于1直接返回该数
1 class Solution { 2 public int findRepeatNumber(int[] nums) { 3 int len = nums.length; 4 // 计数排序,如果数量大于1则返回 5 int[] counts = new int[len]; 6 for(int i = 0; i < len; i++){ 7 counts[nums[i]]++; 8 if(counts[nums[i]] > 1){ 9 return nums[i]; 10 } 11 } 12 return -1; 13 } 14 }
leetcode 运行时间为2ms, 空间为45.9MB
时间复杂度：计数排序，但是不需要统计完，所以平均时间复杂度为O(n/2)
空间复杂度：需要创建一个和nums数组等大的数组，所以空间复杂度为O(n)
在元素不重复的情况下，但数组有序时，每个元素所在的位置和这个元素的值相等。所以我们遍历数组，把当前元素放到正确的位置，也就是以这个元素为下标的位置，把当前元素和他正确的位置的元素进行交换。重新安排位置的过程中，肯定就会有元素重复的情况。返回即可
1 class Solution { 2 public int findRepeatNumber(int[] nums) { 3 int len = nums.length; 4 5 for(int i = 0; i < len; i++){ 6 // 如果当前元素不在正确的位置 7 if(nums[i] != i){ 8 // 如果重复，直接返回 9 if(nums[i] == nums[nums[i]]){ 10 return nums[i]; 11 } 12 // 把当前元素放到正确的位置 13 int temp = nums[nums[i]]; 14 nums[nums[i]] = nums[i]; 15 nums[i] = temp; 16 } 17 } 18 return -1; 19 } 20 }
leetcode运行时间为1ms, 空间为46.3MB
时间复杂度：最多完整的遍历一次数组，平均复杂度为O(n/2)
空间复杂度：O(1)
判断当前元素是否存在于HashSet,如果存在说明是重复元素，直接返回，否则把这个元素存入HashSet
1 class Solution { 2 public int findRepeatNumber(int[] nums) { 3 int len = nums.length; 4 5 HashSet<Integer> hs = new HashSet<Integer>(); 6 for(int num : nums){ 7 if(hs.contains(num)){ 8 return num; 9 } 10 hs.add(num); 11 } 12 return -1; 13 } 14 }
leetcode运行时间为10ms, 空间为47.6MB, 可以看到这个运行时间远大于上面两种方法，所以知道对HastSet虽然也是以hash函数来存取元素的，但是效率远低于直接操作数组。
时间复杂度：最多完整的遍历一次数组，平均复杂度为O(n/2)
空间复杂度：hashset中存储的元素个数，O(n)
leetcode 剑指 Offer 03. 数组中重复的数字
原文：https://www.cnblogs.com/hi3254014978/p/13751247.html