题目描述:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1:
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
注意判定测试用例条件
空指针,或数组长度<0
长度为n的数组中包含0~n-1之外的数字。
方法一:哈希表
利用数据结构特点,容易想到使用哈希表(Set)记录数组的各个数字,当查找到重复数字则直接返回。
当元素存在哈希表中,说明该元素重复,返回该元素,如果不存在,就添加到哈希表中
复杂度分析:
时间复杂度:遍历数组使用O(N,哈希表的添加和查找元素都是O(1)
空间复杂度:使用HashSet占用O(N)的额外空间
public int findRepeatNumber(int[] nums) { /** * 使用哈希表解法 * 时间复杂度:O(N) */ if (nums == null || nums.length <0){ return -1; } for (int i = 0; i<nums.length;i++){ if (nums[i]<0 || nums[i] > nums.length-1){ return -1; } } Set<Integer> set = new HashSet<>(); for (int num : nums) { //元素不在哈希表中,就添加到哈希表,如果存在说明此元素重复,返回此元素 if (set.contains(num)) { return num; } set.add(num); } return -1; }
方法二:原地置换
复杂度分析:
时间复杂度:遍历数组需要O(N),每个数组最多只要交换2次,所以是O(2N),最终时间复杂度:O(N)
空间复杂度:O(1),无需额外空间
class Solution { public int findRepeatNumber(int[] nums) { if(nums == null || nums.length < 0 ){ return -1; } for(int i = 0; i < nums.length ; i++){ if(nums[i] > nums.length - 1){ return -1; } while(nums[i] != i){ if(nums[nums[i]] == nums[i]){ return nums[i]; } int temp = nums[i]; nums[i] = nums[temp]; nums[temp] = temp; } } return -1; } }