题解 | #数组中重复的数字#

空间复杂度 O(n)

数组下标模仿hash表，每出现一次，value+1，知道出现次数=2

import java.util.*;


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

空间复杂度 O(1)

通过交换位置，使得index == value，同时找到相同的value

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