剑指50.数组中重复的数字

import java.util.*;
public class Solution {
    // 使用HashMap
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if (numbers == null || length == 0)
            return false;
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int num : numbers){
            map.put(num,map.getOrDefault(num,0) + 1);
            if (map.get(num) == 2){
                duplication[0] = num;
                return true;
            }
        }
        return false;
    }
    // 使用HashSet
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if (numbers == null || length == 0)
            return false;
        HashSet<Integer> set = new HashSet<>();
        for (int num : numbers){
            if (set.contains(num)){
                duplication[0] = num;
                return true;
            }else{
                set.add(num);
            }
        }
        return false;
    }
}

import java.util.*;
public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if (numbers == null || length == 0)
            return false;
        int[] room = new int[length];
        //Arrays.fill(room,0);   // 辅助数组初始化为0，不加这句也可以
        for (int i = 0; i < length; i++) {
            if (room[numbers[i]] == 0){
                room[numbers[i]]++;
            }else{
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }
}

public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if (numbers == null || length == 0)
            return false;
        for (int i = 0; i < length; i++) {
            while (numbers[i] != i){  // 直到当前i位置 == nums[i]
                if (numbers[numbers[i]] == numbers[i]){
                    duplication[0] = numbers[i];
                    return true;
                }else{
                    // swap
                    int temp = numbers[i];
                    numbers[i] = numbers[temp];
                    numbers[temp] = temp;
                }
            }
        }
        return false;
    }
}