2017-09-15 19:44:15 +0000   |     algorithm leetcode array   |   Viewed times   |    

题目

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]

Set

代码

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        Set<Integer> set = new HashSet<>();
        List<Integer> res = new ArrayList<>();
        for (int num : nums) {
            if (!set.add(num)) { res.add(num); }
        }
        return res;
    }
}

结果

find-all-duplicates-in-an-array-1

直接在原始数组上记录出现信息,

拿到i桶位的数nums[i] = x,那么就把x桶位的数变成负数,nums[x] = -nums[x]。下次x再出现,先检查一下x桶位的数nums[x]是不是负数。

代码

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int num : nums) {
            int offset = Math.abs(num) - 1;
            if (nums[offset] < 0) { res.add(offset+1); }
            nums[offset] = -nums[offset];
        }
        return res;
    }
}

结果

find-all-duplicates-in-an-array-2