LeetCode面试系列 第11天:No.645 - 错误的集合

上一篇 LeetCode 面试题中,我们分析了一道简单的几何数学题。今天我们来分析一道集合相关的数学题。

Leetcode

今天要给大家分析的面试题是 LeetCode 上第 645 号问题,

LeetCode - 645. 错误的集合

https://leetcode-cn.com/problems/set-mismatch/

题目描述

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

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

示例 1:

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

注意:

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

解题思路:

由于给定输入是无序的数组,且每个数的范围是 [1, n] ,排序后便于后续处理。

如何得到重复的数

  • 只需要使用 set 中元素互不相等的特性,得到去除重复后的数组
  • 对原数组求和,再对去重后的数组求和,所得两个和的差极为重复的数

如何得到缺失的数

  • 使用一个对比序列 stdList,放有: 1, 2 … n 等元素 (从 1 到 n)
  • 将原数组转为 set,再将对比序列转为 set。两个 set 的差集中的元素只有一个,取出就是缺失的数。

最后将 重复的数 **和 **缺失的数 一起放进 list 中即可。

AC的代码为:

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        res = list()
        nums.sort()
        stdList = range(1, len(nums) + 1)  # len(nums) = n
        repeatedNum = sum(nums) - sum(set(nums))     
        res.append(repeatedNum)
        missingNum =  (set(stdList) - set(nums)).pop()
        res.append(missingNum)
        return res

执行用时: 276 ms, 在所有 python3 提交中击败了 60.58 % 的用户.

Leetcode645

示例代码: https://github.com/JustDoPython/leetcode-python/tree/master/leetcode-645

Python Geek Tech wechat
欢迎订阅 Python 技术,这里分享关于 Python 的一切。