leetcode-442-Find-All-Duplicates-in-an-Array

发表于   |  

描述

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:

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

Output:
[2,3]

分析

1 ≤ a[i] ≤ n，遍历的时候将 a[i] 的值对应的 a 的值取反，如果遍历过程中这个索引出现负值，则表明出现了两次。原地哈希，不需要额外的空间复杂度。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] < 0) {
                result.add(index+1);
            }
            nums[index] = -nums[index];
        }
        return result;
    }
}

解决方案2（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func findDuplicates(nums []int) []int {
    if len(nums) == 0 {
        return nums
    }
    result := make([]int, 0)
    
    for i := 0; i < len(nums); i++ {
        for nums[i] != nums[nums[i]-1] {
            nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
        }
    }
    
    for i := 0; i < len(nums); i++ {
        if nums[i] != i+1 {
            result = append(result, nums[i])
        }
    }
    return result
}

相关问题

题目来源