645. Set Mismatch

645. Set Mismatch (easy) 错误的集合

题干

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:

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

Example 2:

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

Constraints:

• 2 <= nums.length <= 104
• 1 <= nums[i] <= 104

解题思路

暴力解法

重复的值可以用多一个数据结构来记录是否已经存在过；缺失的值，可以通过循环1-n来查找值是否存在。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

技巧解法

时间复杂度基本上无法优化了，只能优化空间复杂度了。

上面我们是使用了额外的空间记录，来找到重复的值。因为期望的数组是1-n，有问题的数组只是其中一个数字错了，所以还是有数学规律在里面的。

首先，我们先计算三个数值

• sum_expected，将1-n相加，计为(1+n)n/2
• sum_nums，将错误的数组相加
• sum_set，将错误的数组转换成set后相加

获取重复的数值，可以通过sum_nums - sum_set得到

获取缺失的数值，可以通过sum_expected - sum_set得到

时间复杂度无法继续优化，是因为sum()求和函数也是O(n)

我的答案

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        checked_nums = []
        dup_num = 0
        for num in nums:
            if num in checked_nums:
                dup_num = num
                break
            checked_nums.append(num)

        lost_num = 0
        for i in range(1, len(nums)+1):
            if i not in nums:
                lost_num = i
                break

        return [dup_num, lost_num]

技巧答案

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        checked_nums = []

        n = len(nums)
        sum_expected = n * (n + 1) // 2
        sum_nums = sum(nums)
        sum_set = sum(set(nums))

        dup_num = sum_nums - sum_set
        lost_num = sum_expected - sum_set

        return [dup_num, lost_num]

虽然都是O(n)，但是还是建议sum()的方式。源码是C实现，实测性能更好。