leetcode645——错误的集合（easy)

一、题目描述

集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1:

输入: nums = [1,2,2,4]
输出: [2,3]

注意:

给定数组的长度范围是 [2, 10000]。
给定的数组是无序的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/set-mismatch

二、题解

方法一：暴力算法

方法一最容易想到，根据题意，正确的数组nums里面的数字应该为 1~n ，n为数组的长度，那么我们可以直接从1开始与nums数组里面的数字挨个比较。首先使用两个for循环遍历矩阵，外层循环从1到n取值(n为数组的长度），内层循环遍历nums数组。然后设定一个计数器count，记录外层循环值的重复次数；设定一个记录重复值的变量repeat，一个记录缺失值的变量miss。当内层循环结束后，检查count的值，若count为0，则miss记录外层循环的当前值，若count为2，则repeat记录外层循环的当前值。此法时间复杂度太大，运行直接超时，不值得推荐。

完成时间：2020.05.10

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

        repeat, miss = 0, 0 #分别记录重复值和缺失值
        for i in range(len(nums)): # 取1到n的值与nums比较
            count = 0
            for j in range(len(nums)): # 遍历数组nums
                if i + 1 == nums[j]: # 记录从1到n每个值的重复次数
                    count += 1
            if count == 0: # 重复次数为0，表明值缺失
                miss = i + 1
            if count == 2: # 重复次数为2，表明值重复
                repeat = i + 1
            if repeat > 0 and miss > 0: # 若已找到重复值和缺失值，则结束循环
                break
        return repeat, miss

方法一使用了两趟循环：

时间复杂度：(O(n^2)) ，(n)指的是nums数组长度。
空间复杂度：(O(1))。

方法二：使用排序

方法二首先将nums数组升序排列，然后再遍历数组nums，判断nums[i] == nums[i+1]是否成立找到重复数值，判断nums[i] + 1 < nums[i+1]是否成立找到缺失数值。循环结束后再判断一下缺失值是否在数组末尾。

注意：

这种方法要注意缺失值在末尾和头部的情况，即缺失1或n。缺失1的话，可以将miss的初始值置为1即可解决，缺失n的话，循环结束后要判断下nums[i] == len(nums)是否成立，即比较数组最后一个元素与数组的长度是否相等。

完成时间：2020.05.11

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

        nums.sort() # 升序排列
        repeat, miss, i = 0, 1, 0 # 若缺失值在开头，即缺失1，则将miss的初始值设为1
        while i < len(nums)-1: # i从0到n-2，n为数组nums的长度
            if nums[i] == nums[i+1]:  # 记录重复值
                repeat = nums[i]
            if nums[i] + 1 < nums[i+1]: # 记录缺失值，记录缺失值在中间（除了开头和末尾）的值
                miss = nums[i] + 1
            i += 1    
        if nums[i] != len(nums): # 若缺失值在末尾，即缺失n，则将miss的初始值设为n
            miss = len(nums)
        return repeat, miss

方法二使用了一趟排序，一趟循环：

时间复杂度：排序的时间复杂度为(O(log_{2}n))，while循环的时间复杂度为 (O( n )，)(n)指的是数组长度，所以总的时间复杂度为(O(log_{2}n)) 。

空间复杂度：(O(1))。

方法三：将数组元素作为下标

方法三思路很简单，创建一个额外的数组mirrors，所有值处初始化为0，长度为n+1（n为nums数组的长度）。将nums数组的值作为mirrors数组的下标，然后在mirrors[nums[i]]处增加1，表明nums[i]的数量增加1。之后遍历mirrors数组，根据mirrors数组的值判断是重复值还是缺失值。

完成时间：2020.05.11

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        
        mirrors = [0] * (len(nums) + 1) # 构造一个新的数组,数组长度为n+1
        repeat, miss = 0, 0
        # 将nums数组里面的元素作为下标，并下表对应的mirorrs数组值增加1
        for i in range(len(nums)):
            mirrors[nums[i]] += 1
        # 遍历mirrors数组，查看数组值
        i = 1
        while i < len(mirrors):
            if mirrors[i] == 2: # 重复值
                repeat = i
            elif mirrors[i] == 0: # 缺失值
                miss = i
            if repeat > 0 and miss > 0: # 找到重复值和缺失值，马上返回结果
                return repeat, miss
            i += 1

方法三使用了两趟循环，一个额外数组，典型的用空间换时间：

时间复杂度：(O(n))，(n)指的是nums数组的长。
空间复杂度：(O(n))，(n)指的是nums数组的长度。

reference:

https://leetcode-cn.com/problems/set-mismatch/solution/cuo-wu-de-ji-he-by-leetcode/