645. Set Mismatch

Loading...LeetCode

最明显的方法就是 hash map，很简单，但效率不高，不写了。

因为1～n的等差数组，可以用list替代hash-map，减少空间使用，最后找 index 来返回。

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        rank = [0 for _ in range(len(nums))]
        repetition, missing = 0, 1
        for n in nums:
            rank[n-1] += 1
        repetition = rank.index(2)+1
        missing = rank.index(0)+1
        return [repetition, missing]

排序也可以做，排完了遍历，但这个在长度=2的时候有 edge cases，需要注意。

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        nums = sorted(nums)
        repetition, missing = 0, 1
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                repetition = nums[i]
            elif nums[i] < nums[i+1] - 1:
                missing = nums[i] + 1
        if nums[-1] != len(nums):
            missing = len(nums)
        return [repetition, missing]

用set把重复元素去掉的话，set(nums)和目标数组的总和差值就是missing了，目标数组的总和也可以拿等差数列求和来做。

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        sumSet = sum(set(nums))
        missing = int(len(nums)*(1+len(nums))/2-sumSet)
        repetition = sum(nums)-sumSet
        return [repetition, missing]