645. Set Mismatch 错误的集合

题目地址：https://leetcode.com/problems/set-mismatch/description/open in new window

题目描述

Theset S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.

Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Example 1:

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

Note:

The given array size will in the range [2, 10000].
The given array's numbers won't have any order.

题目大意

数组正常的状态是1~N，但是有个数字重复出现了，导致覆盖了另外一个数字，现在要求重复出现的数字，和缺失的数字。

解题方法

Hash方法

这个题明显使用hash的思想。把每个位置出现的次数统计一下，找出出现了2次和0次的数字的位置即可。

class Solution(object):
    def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        hashs = [0] * len(nums)
        missing = -1
        for i in range(len(nums)):
            hashs[nums[i] - 1] += 1
        return [hashs.index(2) + 1, hashs.index(0) + 1]

1 2 3 4 5 6 7 8 9 10 11

直接计算

和268. Missing Numberopen in new window很像，直接计算出来也可以，速度稍快点。

class Solution(object):
    def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        N = len(nums)
        nset = set(nums)
        missing = N * (N + 1) / 2 - sum(nset)
        duplicated = sum(nums) - sum(nset)
        return [duplicated, missing]

1 2 3 4 5 6 7 8 9 10 11

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛授权发布，任何组织或个人未经作者授权不得转发