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

朱雀 2022-11-20 02:58 123阅读 0赞

# 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);
        }
    }