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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */


    public int duplicate (int[] n) {
        for(int i=0;i<n.length;i++){
            while(i!=n[i]){
                if(n[i]==n[n[i]]){
                    return n[i];
                }
                swap(n,i,n[i]);
            }
        }
        return -1;
        // write code here
    }

        public void swap(int[] n,int i,int j){
                int temp = n[i];
                n[i]=n[j];
                n[j]=temp;
    }
}

要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。

对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。在调整过程中，如果第 i 位置上已经有一个值为 i 的元素，就可以知道 i 值重复。

以 (2, 3, 1, 0, 2, 5) 为例，遍历到位置 4 时，该位置上的数为 2，但是第 2 个位置上已经有一个 2 的值了，因此可以知道 2 重复：