算法寻找数组中的重复值，四种解法

寻找数组中的重复值

题目来源于&＃xff1a;Leetcode-287。本题归类到简单我无法理解…要满足四个条件需要用很特定的解法&＃xff0c;面试中要是用到的话很可能是在给自己挖坑&＃xff0c;所以我这里只讲几种能满足一部分条件的解法。

给定一个包含 n &＃43; 1 个整数的数组 nums&＃xff0c;其数字都在 1 到 n 之间&＃xff08;包括 1 和 n&＃xff09;&＃xff0c;可知至少存在一个重复的整数。假设只有一个重复的整数&＃xff0c;找出这个重复的数。示例 1:输入: [1,3,4,2,2]
输出: 2
示例 2:输入: [3,1,3,4,2]
输出: 3
说明&＃xff1a;1、不能更改原数组&＃xff08;假设数组是只读的&＃xff09;。
2、只能使用额外的 O(1) 的空间。
3、时间复杂度小于 O(n2) 。
4、数组中只有一个重复的数字&＃xff0c;但它可能不止重复出现一次。


下面给出四种解法&＃xff0c;
1、第一种基于排序&＃xff0c;大家都懂的&＃xff0c;满足条件2、3、4。时间nlogn,空间n
2、第二种属于元素归位&＃xff0c;其实和缺失最小正数那题挺像的&＃xff0c;不过我们判断的时候&＃xff0c;应当以目标位置中的元素是不是与当前元素重复为依据&＃xff0c;如果索引不一致&＃xff0c;但是值重复了&＃xff0c;那就说明这是一个重复元素&＃xff0c;满足2、3、4并且比排序方式更快。时间n,空间1
3、第三种是利用哈希表&＃xff0c;满足1、3、4 。时间n空间n
4、第四种同样是利用哈希表&＃xff0c;不过该哈希表我们可以自建&＃xff0c;满足1、3、4。时间n空间n

第2类方式是比较好的。

//方式1&＃xff0c;排序,时空复杂度为nlog(n)和O(1)public int findDuplicate(int[] nums) {Arrays.sort(nums);for(int i&＃61;1;i<nums.length;i&＃43;&＃43;){if(num[i]&＃61;&＃61;nums[i-1]){return nums[i];}}return 0;}//方式2&＃xff0c;按照最小缺失正数的思路来解&＃xff0c;即元素归位//在数组中所有元素都处于1-n,我们把元素nums[i]放到i-1的位置//时间复杂度O(N),空间复杂度O(1)public int findDuplicate(int[] nums) {for(int i&＃61;0;i<nums.length;i&＃43;&＃43;){while(i!&＃61;nums[i]-1){if((i!&＃61;nums[i]-1)&&nums[nums[i]-1]&＃61;&＃61;nums[i]){return nums[i];}swap(nums,nums[i]-1,i);}}return 0;}private void swap(int nums[],int i,int j){int temp&＃61;nums[i];nums[i]&＃61;nums[j];nums[j]&＃61;temp;}//方式3&＃xff0c;使用HashSet来映射&＃xff0c;时空复杂度均为O(N)public int findDuplicate(int[] nums) {Set<Integer> set&＃61;new HashSet<>();for(int i&＃61;0;i<nums.length;i&＃43;&＃43;){if(set.contains(nums[i])){return nums[i];}set.add(nums[i]);}return 0;}//方式4&＃xff0c;自建map来映射&＃xff0c;时空复杂度均为O(N)public int findDuplicate(int[] nums) {int[] map&＃61;new int[nums.length];for(int i&＃61;0;i<nums.length;i&＃43;&＃43;){if(map[nums[i]]&＃61;&＃61;1){return nums[i];}map[nums[i]]&＃43;&＃43;;}return 0;}