剑指Offer系列（java版，详细解析） 03. 数组中重复的数字

末蓝、 2022-11-07 04:15 103阅读 0赞

# 题目一 #

## 题目描述 ##

#### [剑指 Offer 03. 数组中重复的数字][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;
        }
    
    }

[Offer 03.]: https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/