剑指Offer面试题：5.找出数组中重复的数字

一、题目
————————————————
在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。
————————————————
二、思路
————————————————
　　从哈希表的思路拓展，重排数组：把扫描的每个数字（如数字m）放到其对应下标（m下标）的位置上，若同一位置有重复，则说明该数字重复。
————————————————
三、解决问题
————————————————
测试用例
　　1.数组中带一个或多个重复数字
　　2.数组中不包含重复的数字
　　3.无效输入测试用例（空数组，数组数字越界等）
————————————————

package swordoffer;

/**
 * @author LQ
 * @version 1.0
 * @date 2020-03-12 22:55
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 在一个长度为n的数组里的所有数字都在0到n-1的范围内。
 * 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
 * 请找出数组中任意一个重复的数字。
 * 例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。
 */

public class Solution05 {
    public static void main(String[] args) {
        System.out.println("==============================");
        Solution05 sword = new Solution05();
        sword.test1();
        System.out.println("==============================");
        sword.test2();
        System.out.println("==============================");
        sword.test3();
        System.out.println("==============================");
        sword.test4();
        System.out.println("==============================");

    }
    /**
     * 方法一：时间复杂度 O(N)，空间复杂度 O(1)
     * 从哈希表的思路拓展，重排数组：
     * 把扫描的每个数字（如数字m）放到其对应下标（m下标）的位置上，
     * 若同一位置有重复，则说明该数字重复。
     * 找到数组中一个重复的数字
     * 返回-1代表无重复数字或者输入无效
     */
    public int getDuplicate01(int[] array) {
        if(null == array || array.length <= 0){
            System.out.println("数组输入无效！");
            return -1;
        }
        //保证数组在一个长度为n的数组里的所有数字都在0到n-1的范围内。
        for(int arr : array){
            if(arr < 0 || arr > array.length - 1){
                System.out.println("数组大小超出范围！");
                return -1;
            }
        }
        //把扫描的每个数字（如数字m）放到其对应下标（m下标）的位置上，
        //若同一位置有重复，则说明该数字重复。
        for (int i = 0; i < array.length; i++) {
            int temp;
            while (array[i] != i){
                if (array[array[i]] == array[i]){
                    return array[i];
                }
                //交换元素
                temp = array[i];
                array[i] = array[temp];
                array[temp] = temp;
            }
        }
        System.out.println("数组中无重复数字！");
        return -1;
    }

    /**
     * 方法二：时间复杂度 O(N)，空间复杂度 O(N)
     * 根据HashMap - 键值唯一的特性解题
     * @param nums
     * @return
     */
    public int getDuplicate02(int[] nums) {
        if(null == nums || nums.length <= 0){
            System.out.println("数组输入无效！");
            return -1;
        }
        //HashMap - 键值唯一 key为数字  value为出现次数
        Map<Integer, Integer> numsMap = new HashMap<>();
        int index = -1;
        for (int i = 0; i < nums.length; i++) {
            //保证数组在一个长度为n的数组里的所有数字都在0到n-1的范围内。
            if (nums[i] < 0 || nums[i] > nums.length - 1) {
                System.out.println("数组大小超出范围！");
                return -1;
            } else if (numsMap.containsKey(nums[i])) {
                //boolean containsKey(Object key)
                //如果此映射包含对于指定键的映射关系，则返回 true：已包含则返回该索引-即在原数组中的位置
                index = i;
            } else {
                //不包含,将该值放入HashMap的键
                numsMap.put(nums[i], 1);
            }
        }
        //nums[index] -- 依据index找到原数组中的元素
        return index == -1 ? -1 : nums[index];
    }
    // ==================================测试代码==================================
    /**
     *数组为null
     */
    public void test1() {
        System.out.println("test1：");
        int[] a = null;
        System.out.println("方法一：");
        int dup = getDuplicate01(a);
        if (dup >= 0){
            System.out.println("重复数字为：" + dup);
        }
        System.out.println("方法二：");
        dup = getDuplicate02(a);
        if (dup >= 0){
            System.out.println("重复数字为：" + dup);
        }
    }

    /**
     *数组无重复数字
     */
    public void test2() {
        System.out.println("test2：");
        int[] a = { 0, 1, 2, 3 };
        System.out.println("方法一：");
        int dup = getDuplicate01(a);
        if (dup >= 0){
            System.out.println("重复数字为：" + dup);
        }
        System.out.println("方法二：");
        dup = getDuplicate02(a);
        if (dup >= 0){
            System.out.println("重复数字为：" + dup);
        }
    }

    /**
     *数组数字越界
     */
    public void test3() {
        System.out.println("test3：");
        int[] a = { 1, 2, 3, 4 };
        System.out.println("方法一：");
        int dup = getDuplicate01(a);
        if (dup >= 0){
            System.out.println("重复数字为：" + dup);
        }
        dup = 0;
        System.out.println("方法二：");
        dup = getDuplicate02(a);
        if (dup >= 0){
            System.out.println("重复数字为：" + dup);
        }
    }

    /**
     *数组带重复数字
     */
    public void test4() {
        System.out.println("test4：");
        int[] a = { 1, 2, 3, 2, 4 };
        System.out.println("方法一：");
        int dup = getDuplicate01(a);
        if (dup >= 0){
            System.out.println("重复数字为：" + dup);
        }
        dup = 0;
        System.out.println("方法二：");
        dup = getDuplicate02(a);
        if (dup >= 0){
            System.out.println("重复数字为：" + dup);
        }
    }
}

努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。