题目一

题目描述

剑指 Offer 03. 数组中重复的数字

难度简单

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

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

限制：

2 <= n <= 100000

测试用例

• 长度为n的数组包含一个或多个重复的数字。
• 数组中不包含重复的数字。
• 无效输入测试用例（输入数组为空；程度为n的数组中包含 0 到 n-1之外的数字）

题目考点

• 考察应聘者对以为数组的理解及编程能力。一维数组在内存中占据连续的空间，因此我们可以根据下标定位对应的元素。
• 考察应聘者分析问题的能力，当应聘者发现问题比较复杂的时候，能不能通过具体的例子来找出其中的规律。

解题思路

差（时间复杂度为O(nlogn)，空间复杂度为O(1)）

先对数组排序，然后从头扫描排序后的数组就可以了。

中（时间复杂度为O(n)，空间复杂度为O(n)）

从头到尾按顺序扫描数组的每个数字，每扫描到一个数字的时候就判断该哈希表是否已经存在该数字，如果哈希表还没有这个数字，就把它加入到哈希表中，如果哈希表已经有这个数字，就找到了一个重复的数字。

好（时间复杂度为O(n)，空间复杂度为O(1)）

关键：这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素放到第 i 个位置上。

从头到尾依次扫描这个数字中的每个数字，当扫描到下标为i的数字，首先比较这个数字（用m表示）是不是等于i，如果是，则继续扫描下一个，如果不是，就就拿它和第m个数字比较，如果它和第m个数字相等，就找到了一个重复的数字；如果不相等，就把第i个数字与第m个数字交换，把m放到属于它的位置，接下来再重复这个比较，交换的过程，直到我们发现一个重复的数字。

具体过程：（以输入{2, 3, 1, 0, 2, 5}为例）

position-0 : (2,3,1,0,2,5) // 2 <-> 1
             (1,3,2,0,2,5) // 1 <-> 3
             (3,1,2,0,2,5) // 3 <-> 0
             (0,1,2,3,2,5) // already in position
position-1 : (0,1,2,3,2,5) // already in position
position-2 : (0,1,2,3,2,5) // already in position
position-3 : (0,1,2,3,2,5) // already in position
position-4 : (0,1,2,3,2,5) // nums[i] == nums[nums[i]], exit

正确解题（最佳）

/**
 * Author:Viper
 * Data:2021/3/10
 * description:
 */
public class problem03 {
    public static int findRepeatNumber(int[] nums){
        if(nums.length==0){
            return -1;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]<0 || nums[i]>nums.length-1) {
                return -1;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            while(nums[i]!=i){
                if(nums[i]==nums[nums[i]]){
                    return nums[i];
                }
                int tmp = nums[i];
                nums[i]=nums[tmp];
                nums[tmp]=tmp;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array=new int[]{2,3,1,0,2,5,3};
        System.out.println(findRepeatNumber(array));

    }
}

题目二

题目描述

不修改数组找出重复的数字。

在一个长度为 n+1 的数组里的所有数字都在 1 到 n 的范围内。 所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字。但不能修改输入的数组。例如，如果输入长度为 7 的数组 {2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是第一个重复的数字 2 或 3 。

测试用例

• 长度为n的数组里包含一个或多个重复的数字。
• 数组中不包含重复的数字。
• 无效输入测试用例（输入数组为空；程度为n的数组中包含 1 到 n 之外的数字）

题目考点

• 考察应聘者对一维数组的理解及编程能力。一维数组在内存中占据连续的空间，因此我们可以根据下标定位对应的元素。
• 考察应聘者对 二分查找算法 的理解，并能快速、正确地实现二分查找算法的代码。
• 考察应聘者的 沟通能力 应聘者只有具备 良好的沟通能力， 充分了解面试官的需求 （只需要找出一个重复数字即可，还有需要不修改数组，还有是注重空间复杂度还是时间复杂度）从而有针对性地选择算法解决问题。

解题思路

思路一（时间复杂度为O(n),空间复杂度为O(n)）

• 创建一个长度为 n+1 的辅助数组，然后逐一吧原数组赋值到辅助数组，如果被赋值的数字是m，则把它赋值到辅助数组中下标为m的位置。这样是很容易发现哪个数字是重复的。
• 从头到尾按顺序扫描数组的每个数字，每扫描到一个数字的时候就判断该哈希表是否已经存在该数字，如果哈希表还没有这个数字，就把它加入到哈希表中，如果哈希表已经有这个数字，就找到了一个重复的数字。

思路二（时间复杂度为O(nlogn),空间复杂度为O(1)）

我们把从 1 到 n 的数字从中间的数字 m 分为两步，前面一半为 1 到 m ，后面一半为 m+1 到 n 。如果 1 到 n 的数字的数目超过 m ，那么这一半里面一定包含重复的数字；否则另一半 m+1 到 n 的区间里一定包含重复的数字。我们可以继续吧包含重复数字的区间一分为二，知道找到一个传给你付的数字。这个过程和 二分查找算法 很类似，只是多了异步统计区间数字的数目。

具体过程：（以输入{2, 3, 5, 4, 3, 2, 6, 7}为例）

step-1 : m=4 and count(<=4 && >=1) = 5 => duplicaiton in [1,2,3,4]
step-2 : m=2 and count(<=2 && >=1) = 2 => duplicaiton in [3,4]
step-3 : m=3 and count(<=3 && >=3) = 2 => duplicaiton in [3,3]
step-4 : end = start and count(<=3 && >=3) = 2 => duplicaiton = 3

PS：这种思路比思路一的时间复杂度高，相当于以时间换空间。

正确解题

/**
 * 不修改数组找出重复的数字
 * 确保空间复杂度为O(1)
 *
 */
public class Duplicate2 {
    /**
     * @param intArray    输入数组
     * @param duplicaiton 将首次找到的重复数字利用duplicaiton[0] = ?存入数组
     * @return 如果输入数组无效返回false，duplicaiton[0]=-1
     */
    public static boolean findDuplicate(int[] intArray, int[] duplicaiton) {
        // 杜绝数组为空
        if (intArray.length == 0) {
            duplicaiton[0] = -1;
            return false;
        }
        // 杜绝数组有非法数字
        for (int i = 0; i < intArray.length; i++) {
            if (intArray[i] < 1 || intArray[i] > intArray.length - 1) {
                duplicaiton[0] = -1;
                return false;
            }
        }
        int start = 1;
        int end = intArray.length - 1;

        while (end >= start) {
            // >> 右移一位相当于除以2
            int middle = ((end + start) >> 1);
            int count = countRange(intArray, start, middle);
            // 终止条件
            if (start == end) {
                if (count > 1) {
                    duplicaiton[0] = middle;
                    return true;
                } else {
                    break;
                }
            }
            if (count > (middle - start) + 1) {
                end = middle;
            } else {
                start = middle + 1;
            }

        }
        duplicaiton[0] = -1;
        return false;

    }

    /**
     * @param intArray 输入数组
     * @param start    区间起始数字
     * @param end      区间结束数字
     * @return 个数
     * @Description 统计数组在区间里数字的个数
     */
    public static int countRange(int[] intArray, int start, int end) {
        if (intArray.length == 0) {
            return 0;
        }
        int count = 0;
        for (int i : intArray) {
            if (i >= start && i <= end) {
                count++;
            }
        }
        return count;
    }

补充（二分查找法）

/**
 * 二分查找法
 */
public class BinarySearch {
    /**
     * 使用递归的二分查找
     *
     * @param arr 有序数组
     * @param key 待查找关键字
     * @return 找到的位置
     */
    public static int recursionBinarySearch(int[] arr, int key, int low, int high) {
        if (arr.length == 0) {
            return -1;
        }
        if (key < arr[low] || key > arr[high] || low > high) {
            return -1;
        }
        int middle = (high - low) >> 2;
        if (arr[middle] > key) {
            //比关键字大则关键字在左区域
            return recursionBinarySearch(arr, key, low, middle - 1);
        } else if (arr[middle] < key) {
            //比关键字小则关键字在右区域
            return recursionBinarySearch(arr, key, middle + 1, high);
        } else {
            return middle;
        }
    }

    /**
     * 不使用递归的二分查找
     * @param arr
     * @param key
     * @return 关键字位置
     */
    public static int commonBinarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;

        if (key < arr[low] || key > arr[high] || low > high) {
            return -1;
        }

        while (low <= high) {
            int middle = (low + high) >> 2;
            if (arr[middle] > key) {
                //比关键字大则关键字在左区域
                high = middle - 1;
            } else if (arr[middle] < key) {
                //比关键字小则关键字在右区域
                low = middle + 1;
            } else {
                return middle;
            }
        }

        return -1;
    }

}