442. Find All Duplicates in an Array

題目敘述

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

Example 1:

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

Input: nums = [1,1,2] Output: [1] Example 3:

Input: nums = [1] Output: []

Constraints:

• n == nums.length
• 1 <= n <= 10**5
• 1 <= nums[i] <= n
• Each element in nums appears once or twice.

題目翻譯

提供一個整數的陣列 nums，集中包含有 n 個元素。每個整數的元素會出現 1 或 2 次。要出出現過 2 次的元素並回傳

解法解析

這題特別要求讓 Time complexity 在 O(n)。個人覺得這題應該只有 Easy 才對，不知道為什麼分配到 Medium，可能因為有要求 Time complexity 吧。 最基本的解法就是使用一個 Set 或是 Array，紀錄已經出現過的元素。

程式範例

Python

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        seen = set()
        return [x for x in nums if x in seen or seen.add(x)]

JavaScript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function (nums) {
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        const cur = Math.abs(nums[i]);

        if (nums[cur - 1] < 0) {
            result.push(cur);
        }

        nums[cur - 1] *= -1;
    }

    return result;
};

Go

func findDuplicates(a []int) []int {
    ans := make([]int, 0)
    for _, currentNumber := range a {
        rightIndex := abs(currentNumber) - 1
        if a[rightIndex] < 0 {
            ans = append(ans, rightIndex+1)
        } else {
            a[rightIndex] *= -1
        }
    }
    return ans
}

func abs(a int) int {
    if a < 0 {
        return a * -1
    }
    return a
}

Swift

class Solution {
    func findDuplicates(_ nums: [Int]) -> [Int] {
        var frequencyArr = Array(repeating: 0, count: nums.count)
        var result = [Int]()
        for num in nums {
            frequencyArr[num - 1] = frequencyArr[num - 1] + 1
            if frequencyArr[num - 1] == 2 {
                result.append(num)
            }
        }
        return result
    }
}

Kotlin

class Solution {
    fun findDuplicates(nums: IntArray): List<Int> {
        val seen = mutableSetOf<Int>()
        val result = mutableListOf<Int>()

        for (number in nums) {
            if (seen.contains(number)) {
                result.add(number)
            } else {
                seen.add(number)
            }
        }

        return result
    }
}