剑指offer面试题3：数组中重复的数字

一、知识点：

数组相关知识

二、描述

在一个长度为n的数组里的所有数字都在0~n-1范围内，数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道重复几次。请找出数组中任意一个重复的数字，例如：输入长度为7的数组[2,3,2,4,3,3,5]，那么输出2或者3都是正确的，存在不合法的输入的话输出-1。

数据范围：0≤n≤10000 

进阶：时间：时间复杂度O(n)，空间复杂度O(n)

三、代码

3.1方法一：位置重排（O(n),O(1)）

3.1.1思路

长度为n的数组中数字都在0~n-1范围内，如果这个数组中没有重复的数字，那么数组排序之后数字i将出现在下标为i的位置，由于数组中有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有数字。

3.1.2具体做法

从头到尾依次扫描数组中的每个数字，当扫描到下标为i的数字时，首先比较这个数字（值记为m）是不是i

如果m == i，那么继续扫描下一个数字

如果m != i，那么就拿这个数字和第m个位置上的数值进行比较

如果两个值相等，则找到重复数字

如果不相等，则交换第i位上的数字和第m位上的数字，

接下里进行重复比较、交换的过程，直到找到重复的数字。

数组存放原则：numbers[i] = i

遍历数组所有元素，交换不符合数组存放原则的元素：

例如[2,3,1,0,2]

遍历0位元素2：（交换0位元素2和2位元素1）->[1,3,2,0,2]

遍历0位元素1：（交换0位元素1和1位元素3）->[3,1,2,0,2]

遍历0位元素3：（交换0位元素3和3位元素0）->[0,1,2,3,2]

依次遍历0、1、2、3位置元素，都符合存放原则numbers[i] = i，不做任何操作

遍历末位元素2，此时末位元素2和2位元素2相等，出现了两次，即数字2位重复元素

3.1.3图示

3.1.4Java实现

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        // write code here
        int length = numbers.length;
        if(length == 0) 
            return -1;
        for(int i = 0; i < length; i++){
        	if(numbers[i] < 0 || numbers[i] > length -1)
                return -1;
        }
        for(int i = 0; i < length; i++){
        	while(numbers[i] != i){
                int temp = numbers[i];
                if(temp == numbers[temp])
                    return temp;
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return -1;
    }
}

3.2方法二：使用Java的set特性

3.2.1Java代码

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < numbers.length; i++) {
            if (!set.add(numbers[i])) {
                return numbers[i];
            }
        }
        return -1;
    }
}

3.3方法二：使用Hashmap结构

3.3.1Java代码

import java.util.*;

public class Solution {
    public int duplicate (int[] numbers) {
        int len=numbers.length;
        if(len==0 ||len==1)
            return -1;
        HashMap<Integer,Boolean> map=new HashMap<Integer,Boolean>();
        for(int i=0;i<len;i++){
            //若已存在，则插入为true，否则插入为false
            map.put(numbers[i],map.containsKey(numbers[i]));
        }
        for(int i=0;i<len;i++){
            if(map.get(numbers[i]))
                return numbers[i];
        }
        return -1;
    }
}