Java實作 LeetCode 442 數組中重複的資料

442. 數組中重複的資料

給定一個整數數組 a，其中1 ≤ a[i] ≤ n （n為數組長度）, 其中有些元素出現兩次而其他元素出現一次。

找到所有出現兩次的元素。

你可以不用到任何額外空間并在O(n)時間複雜度内解決這個問題嗎？

* 這個題屬于技巧題 首先仔細看輸入的給定的數組值 該值的區間為 1 ≤ a[i] ≤ n
 * 這其實是這道題解題的關鍵點，好好利用這個資訊。 某些元素出現了兩次，
 * 而一些其他的元素隻出現了1次，我們可以利用這些元素在出現次數上面的不一樣做文章。
 *
 * 仔細觀察發現1 ≤ a[i] ≤ n 這個條件，正好和我們數組的下标差1，我們可以按照數值
 * 來周遊數組，那麼在數組中具有相同值的元素，會被經過兩次，那麼我們隻要想出一種方式
 * 在這個周遊結束後可以區分，哪些元素被經過了多次即可，由于數組元素具有1 ≤ a[i] ≤ n
 * 這樣的範圍，那其實我們當每次經過一個元素時，給他加上n，當周遊結束時，我們再次周遊數組
 * 那些數值超過2n的元素索引+1，對應的就是我們的出現了兩次的元素。
           

class Solution {
    
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> ret = new ArrayList<>();

        int n = nums.length;
        for(int i = 0; i < n; i++){
            nums[(nums[i] - 1) % n] += n;
        }

        for(int i = 0; i < n; i++){
            if(nums[i] > 2 * n) ret.add(i+1);
        }
        return ret;
    }
}