leetcode442. Find All Duplicates in an Array

yimo 發(fā)布于2019-08-16 18:27 / 3347人閱讀

摘要：題目要求存在一個整數(shù)數(shù)組，其中的所有元素都位于之間，其中是數(shù)組的長度。有的元素出現(xiàn)了一次，而有的元素出現(xiàn)了兩次。思路一交換為了在的時間內(nèi)找到所有的出現(xiàn)兩次的數(shù)字，其核心要求在于用現(xiàn)有的數(shù)組記錄已經(jīng)訪問過的元素，同時不會丟失尚未訪問過的元素。

題目要求

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

存在一個整數(shù)數(shù)組，其中的所有元素都位于1~n之間，其中n是數(shù)組的長度。有的元素出現(xiàn)了一次，而有的元素出現(xiàn)了兩次。找到數(shù)組中所有出現(xiàn)兩次的數(shù)字。

思路一：交換

為了在O(N)的時間內(nèi)找到所有的出現(xiàn)兩次的數(shù)字，其核心要求在于用現(xiàn)有的數(shù)組記錄已經(jīng)訪問過的元素，同時不會丟失尚未訪問過的元素。思路一采用交換的核心思想，即每次都將當(dāng)前下標(biāo)上的值和以該值為下標(biāo)的位置上的值進行交換，如果該值下標(biāo)位置上的值和其相等，則說明該數(shù)字已經(jīng)被遍歷過一遍了。

代碼如下：

    public List findDuplicates(int[] nums) {
        int index = 0;
        List result = new ArrayList();
        while(index < nums.length) {
            int num = nums[index];
            if(num == 0){
                index++;
            }else if (nums[num-1] == num) {
                if(index != num-1){
                    result.add(num);
                    nums[index] = 0;
                }
                index++;
            }else{
                swap(index, num-1, nums);
            }
        }
        return result;
    }
    
    public void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

思路二：取反

有沒有一種辦法在既保留當(dāng)前位置上的值nums[i]的同時，又能夠用某種方式記錄i+1是否已經(jīng)被訪問過了？可以通過取反的方法來記錄是否被訪問過這個情況。如果訪問到下標(biāo)為i的位置上的值，則去判斷nums[nums[i]-1]位置上的值是否為負數(shù)，如果是，則說明num[i]出現(xiàn)了兩次，否則將nums[nums[i]-1]位置上的值取反保留。

代碼如下：

    public List findDuplicates(int[] nums) {
        List res = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            int index = Math.abs(nums[i])-1;
            if (nums[index] < 0)
                res.add(Math.abs(index+1));
            nums[index] = -nums[index];
        }
        return res;
    }