数组中重复的数字【Java版】

方法一：排序寻找法（最优）

//【题目特殊条件】一个长度为n的数组里的所有数字都在0到n-1的范围内。
//所以想到：特殊条件下的排序。时间只需要O(n),而不是O(nlogn)
//排序方法：【for+while双重循环】【交换 numbers[numbers[i]] 和 numbers[i]】
public class Solution {
    public int duplicate (int[] numbers) {
        if(numbers == null && numbers.length==0)return -1;//不合法
        for(int i=0; i<=numbers.length-1; ++i){
        //这里虽然是for+while双重循环,但实际上每次交换都会有一个数字到自己的最终排序位置上 =>时间复杂度不是O(n^2),而是O(n)
            while(numbers[i] != numbers[numbers[i]]){//一改一串到底
                int temp = numbers[numbers[i]];
                numbers[numbers[i]] = numbers[i];//建议先改numbers[numbers[i]]，再改numbers[i]  //不然会干扰
                numbers[i] = temp;
            }
            if(i != numbers[i])return numbers[i];//发现重复目标  //一定要放在交换的后面，而不是前面
        }
        return -1;//没找到重复目标=>说明输入是0~n-1都有,则原numbers[]数组已经在O(N)时间内排好序了
    }
}
//时间复杂度：O(N)
//空间复杂度：O(1)

方法二：HashSet
此方法没有利用题目的特性，时间+空间效率，都比方法一要低；
但优点是：1. 不破坏原有数组 2.比较通用，容易想到 3.代码简单，又快又不容易错

import java.util.*;

public class Solution {
    public int duplicate (int[] numbers) {
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i=0; i<=numbers.length-1; ++i){
            if(set.contains(numbers[i]))return numbers[i];
            else set.add(numbers[i]);
            //利用set的STL性质（add时有重复返回false）可以优化效率，将上面两句替换为：
            //if(!set.add(numbers[i]))return numbers[i];
        }
        return -1;
    }
}
//时间: HashSet/HashMap比较复杂，要根据N的规模分类讨论
//空间  O(N)