This page looks best with JavaScript enabled

Leetcode 442 Find All Duplicates in an Array

題目大意

給一長度為 n 的 array, 其元素屬於正整數,介於區間 [1, n], 並且元素最多重複兩次, 找出重複兩次的元素

Problem

Medium

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 <= 105
  • 1 <= nums[i] <= n
  • Each element in nums appears once or twice.

My Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def findDuplicates(self, nums):
        """
        0 1 2           (appears)
        + + +           (original)
        + - -           (1st for loop)
        + + [+, then -] (2nd for loop)
        """
        for i in range(len(nums)):
            idx = abs(nums[i]) - 1
            nums[idx] = -abs(nums[idx])
        for i in range(len(nums)):
            idx = abs(nums[i]) - 1
            nums[idx] *= -1
        return (
            i+1 for i in range(len(nums)) if nums[i] < 0
        )

題目要求 O(n) time and uses only constant extra space.

故使用兩次迴圈 (O(2n) = O(n)), 透過操作元素利用其相反數作為額外紀錄空間

第一次迴圈將使用到的位置直接標為負數, 標示後, 有使用到的位置皆為負

第二次則標示為相反數, 如此第一次使用時由負轉正, 但是若被第二次使用, 則由正轉負

最後回傳負即為答案


補充

看到有人這樣做, 因為說回傳的資料不算空間, 甘安捏 T_T

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution(object):
    def findDuplicates(self, nums):
        res = []
        for n in nums:
            idx = abs(n) - 1
            if nums[idx] > 0:
                nums[idx] *= -1
            else:
                res.append(abs(n))
        return res