数组中重复的数据

Leetcode Link: 442. 数组中重复的数据 - 力扣（LeetCode）

题目

解法一

思路： 类似计数排序

题解： 时间 $O(N)$， 空间 $O(1)$

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        idx = 0
        while(idx<len(nums)):
            val = nums[idx]
            if val == idx + 1:
                idx += 1
                continue
            
            if val == nums[val-1]:
                res.append(nums[idx])
                idx += 1
            else:
                nums[idx], nums[val-1] = nums[val-1], nums[idx]
        
        return list(set(res))

解法二

思路： 或者遇到的就标记。不用换位，自己本身就当作标记数组了 即自己标记自己。对应位置的正负表示索引val遇到了没有。

题解：

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for val in nums:
            if nums[val - 1] > 0:
                nums[val - 1] = -nums[val - 1]
            else:
                res.append(val)
        return res

启发和联系