剑指offer03-寻找一维数组中重复的数字

本文主要是介绍剑指offer03-寻找一维数组中重复的数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.题目描述

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

 Input:{2, 3, 1, 0, 2, 5}​Output:2

2.题目解析

case1： 一维数组在内存中占据连续的空间，因此我们可以根据下标定位对应的元素，总时间复杂度是O(n)，空间复杂度是O(1)

case2： 不修改数组找出重复的数字，我们可以借助一个辅助数组，需要O(n)空间

case3： 不修改数组找出重复的数字，我们尝试使用二分查找方式，如果输入长度n的数组，总时间复杂度为O(nlogn),空间复杂度是O(1)，与case2相比相当于以时间换空间。需要指出这种算法没法找出所有重复的数字

收获：要学会根据面试官要求，是找出任意一个还是全部重复数字，性能上，是时间效率优先还是空间效率优先。选择的算法也是不同的，需要和面试官交流。

3.代码-根据数组下标

package cn.swordOffer.num01;/*** @author GONG* @version 1.0* @date 2020/11/17 10:20* 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1* 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，* 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字* eg：{2, 3, 1, 0, 2, 5, 3}，返回2或者3*/
public class FindDuplicateElementsByIndex {public int getDuplicate(int[] nums) {int res = -1;int len = nums.length;// 判空if (len <= 0) return -1;for (int i = 0; i < len; i++) {//有[0, n-1]范围外的数据if (nums[i] < 0 || nums[i] > len - 1) return -1;// 如果数组下标不等于数据中的值while (nums[i] != i) {// 如果相同表示，出现了重复数字if (nums[i] == nums[nums[i]])return nums[i];// 如果不相同，交换两个位置，交换之后，有个位置 nums[i]=i// 注意交换的顺序，如果temp = num[i]是不可以的int temp = nums[nums[i]];nums[nums[i]] = nums[i];nums[i] = temp;}
//            System.out.println(i + "=========" + Arrays.toString(nums));}return res;}public static void main(String[] args) {FindDuplicateElementsByIndex f = new FindDuplicateElementsByIndex();int nums[] = {2, 3, 1, 1, 0, 5, 4};int ans = f.getDuplicate(nums);System.out.println((ans == -1) ? "没有重复数字" : "其中重复数字是" + ans);}
}

4.代码-原数组上面使用二分查找法

package cn.swordOffer.num01;import java.util.Arrays;/*** @author GONG* @version 1.0* @date 2020/11/17 10:20* <p>* 给定一个数组，查找其是否有重复元素，如果有，任意返回一个重复元素* eg：{2, 3, 1, 0, 2, 5, 3}，返回2或者3*/
public class FindDuplicateElementsByBinarySearch {public int getDuplicate(int[] nums) {// 判空int len = nums.length;if (len <= 0) return -1;// 使用二分法int start = 0;int end = len - 1;while (end >= start) {int middle = start + (end - start) / 2;// 判断在某个区间内，出现的数字个数，比如在0-2区间，如果出现了4个数字，那么肯定是出现了重复数字了int countByRange = countRange(nums, len, start, middle);// 求到了最后，指针指向了同一个位置if (start == end) {if (countByRange > 1) return start;else break;}// 缩小区间，如果前面区间满足条件，end前移，如果前面不满足条件，start后移if (countByRange > (middle - start + 1)) end = middle;else start = middle + 1;}return -1;}// 查找start 到 end 这个区间内，数组中出现的数字一共有多少个？private int countRange(int[] nums, int len, int start, int end) {int count = 0;for (int i = 0; i < len; i++) {if (nums[i] >= start && nums[i] <= end)++count;}return count;}public static void main(String[] args) {FindDuplicateElementsByBinarySearch f = new FindDuplicateElementsByBinarySearch();int nums[] = {2, 3, 1, 0, 2, 5, 3};int ans = f.getDuplicate(nums);System.out.println((ans == -1) ? "没有重复数字" : "其中重复数字是" + ans);}
}

 

这篇关于剑指offer03-寻找一维数组中重复的数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---