題目描述

在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)谋竖。 數(shù)組中某些數(shù)字是重復(fù)的尚蝌，但不知道有幾個(gè)數(shù)字是重復(fù)的瑟幕。也不知道每個(gè)數(shù)字重復(fù)幾次磕蒲。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。 例如只盹，如果輸入長(zhǎng)度為7的數(shù)組{2,3,1,0,2,5,3}辣往，那么對(duì)應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字2。

時(shí)間限制：1秒 空間限制：32768K

public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    這里要特別注意~返回任意重復(fù)的一個(gè)殖卑，賦值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
    
    }
}

解題思路

1站削、使用LinkedHashSet：既保持元素的插入順序又保證了查找元素的效率

import java.util.LinkedHashSet;
public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        LinkedHashSet<Integer> hs=new LinkedHashSet<>();
        for(int i=0;i<length;i++){
            if(!hs.isEmpty()&&hs.contains(numbers[i])){
                duplication[0]=numbers[i];
                return true;
            }
            hs.add(numbers[i]);
        }
        return false;
    }
}

2、利用特性
見(jiàn)https://blog.nowcoder.net/n/808e31c3b2424647a3743aad6e2831e7?f=comment

數(shù)組的長(zhǎng)度為 n 且所有數(shù)字都在 0 到 n-1 的范圍內(nèi)孵稽，我們可以將每次遇到的數(shù)進(jìn)行"歸位"钻哩，當(dāng)某個(gè)數(shù)發(fā)現(xiàn)自己的"位置"被相同的數(shù)占了屹堰，則出現(xiàn)重復(fù)。
掃描整個(gè)數(shù)組街氢，當(dāng)掃描到下標(biāo)為 i 的數(shù)字時(shí)扯键，首先比較該數(shù)字（m）是否等于 i，如果是珊肃，則接著掃描下一個(gè)數(shù)字荣刑；如果不是，則拿 m 與第 m 個(gè)數(shù)比較伦乔。如果 m 與第 m 個(gè)數(shù)相等厉亏，則說(shuō)明出現(xiàn)重復(fù)了；如果 m 與第 m 個(gè)數(shù)不相等烈和，則將 m 與第 m 個(gè)數(shù)交換爱只，將 m "歸位"，再重復(fù)比較交換的過(guò)程招刹，直到發(fā)現(xiàn)重復(fù)的數(shù)

舉個(gè)栗子：

以數(shù)組 {2,3,1,0,2,5,3} 為例
當(dāng) i = 0 時(shí)恬试，nums[i] = 2 != i，判斷 nums[i] 不等于 nums[nums[i]]疯暑，交換 nums[i] 和 nums[nums[i]]训柴，交換后數(shù)組為：{1,3,2,0,2,5,3}
此時(shí) i = 0，nums[i] = 1 != i妇拯，判斷 nums[i] 不等于 nums[nums[i]]幻馁，交換 nums[i] 和 nums[nums[i]]，交換后數(shù)組為：{3,1,2,0,2,5,3}
此時(shí) i = 0越锈，nums[i] = 3 != i仗嗦，判斷 nums[i] 不等于 nums[nums[i]]，交換 nums[i] 和 nums[nums[i]]甘凭，交換后數(shù)組為：{0,1,2,3,2,5,3}
此時(shí) i = 0儒将，nums[i] = 0 = i，繼續(xù)下一組
當(dāng) i = 1对蒲，nums[i] = 1 = i钩蚊，繼續(xù)下一組
當(dāng) i = 2，nums[i] = 2 = i蹈矮，繼續(xù)下一組
當(dāng) i = 3砰逻，nums[i] = 3 = i，繼續(xù)下一組
當(dāng) i = 4泛鸟，nums[i] = 2 != i蝠咆，判斷 nums[i] 等于 nums[nums[i]]，出現(xiàn)重復(fù)，賦值返回

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){
                if(numbers[i] == numbers[numbers[i]]){
                    duplication[0] = numbers[i];
                    return true;
                }
                // swap
                int tmp = numbers[i];
                numbers[i] = numbers[tmp];
                numbers[tmp] = tmp;
            }
        }
        return false;
    }
}