1.找出数组中重复的数字 ----《剑指Offer》题解(Java)

不念不忘少年蓝@ 2021-10-24 00:54 284阅读 0赞

## 题目 ##

给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；

样例  
给定 nums = \[2, 3, 5, 4, 3, 2, 6, 7\]。

返回 2 或 3。

## 算法思路 ##

找重复数字可以直接用HashMap来解决，但需要额外的空间。  
本题可以只用O(1)的空间复杂度来实现，具体思路是：  
由于数字范围是\[0, n-1\],数组长度是n，因此可把数组当做是数字的槽位，依次将数字放到对应数组下标的位置去。  
遍历数组，将当前元素nums\[i\]放到它对应的数组下标的位置去，即swap(nums\[i\] , nums\[nums\[i\]\])，注意交换到位置i的数字也要继续放到它相应的槽去，依次循环直到当前位置i放入了正确的数字，即nums\[i\] == i。  
假如在将当前位置的元素放到正确位置的时候，发现该位置已经是正确的数字了，说明有重复，直接返回该数字即可。  
需要注意，题目中“如果某些数字不在 0∼n−1 的范围内，则返回 -1”，这是个坑，需要提前判断，如果在遍历数组中判断则可能先找到重复元素，就退出，超出范围的数还没被判断到。  
算法的时间复杂度是O(n)

## 代码实现 ##

class Solution { public int duplicateInArray(int[] nums) { if (nums == null || nums.length == 0) return -1; int n = nums.length; //提前遍历判断"如果某些数字不在 0∼n−1 的范围内,则返回 -1" for (int i=0; i<n; i++) { if (!(nums[i] >= 0 && nums[i] < n)) return -1; } for (int i=0; i<n; i++) { //循环将当前位置的元素放到对应的槽去 while (nums[i] != nums[nums[i]]) swap(nums, i, nums[i]); //当前元素应该放到对应位置，但该位置的数字跟当前的一样，即重复了 if (nums[i] != i && nums[i] == nums[nums[i]]) return nums[i]; } return -1; } //交换数组两个元素 private void swap(int[] nums, int i, int j) { nums[i] = nums[i] ^ nums[j]; nums[j] = nums[i] ^ nums[j]; nums[i] = nums[i] ^ nums[j]; } }

转载于:https://www.cnblogs.com/TatuCz/p/11113088.html