专栏首页木又AI帮【leetcode刷题】T53-错误的集合

【leetcode刷题】T53-错误的集合

【题目】

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

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

示例 1:

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

注意:

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

【思路】

最直接的想法:使用字典,key为元素,value为出现次数,找到次数为2的元素;接着从1到n遍历,判断哪个元素不再字典中。

另外一种奇妙的想法:计算所有元素的和sum1;使用set求得唯一元素,计算其和sum2;同时计算1到n的和sum3=1+2+…+n=n*(n+1)/2;那么缺失的元素为sum3-sum2,多余的元素为sum1-sum2。

【代码】

python版本

方法一

class Solution(object):
    def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        d = {}
        for n in nums:
            d[n] = d.get(n, ) + 
        res = [, ]
        for i in range(, len(nums)+):
            if i not in d:
                res[] = i
            elif d[i] == :
                res[] = i
        return res

方法二

class Solution(object):
    def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        length = len(nums)
        sum1 = length * (length+) / 
        sum2 = sum(set(nums))
        return [sum(nums) - sum2, sum1 - sum2]

C++版本

方法一

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int length = nums.size();
        map<int, int> d;
        vector<int> res;
        for(auto n:nums){
            if(d.find(n) == d.end())
                d[n] = ;
            else
                res.push_back(n);
        }
        for(int i=; i<length+; i++){
            if(d.find(i) == d.end()){
                res.push_back(i);
                break;
            }
        }
        return res;
    }
};

方法二

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int length = nums.size();
        int sum1 = length * (length+) / ;
        int sum2 = ;
        int repeat_num;
        map<int, int> d;
        for(auto n: nums){
            sum2 += n;
            if(d.find(n) == d.end())
                d[n] = ;
            else
                repeat_num = n;
        }
        vector<int> res;
        res.push_back(repeat_num);
        res.push_back(sum1 - (sum2 - repeat_num));
        return res;
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】20T16-移除元素

    https://leetcode-cn.com/problems/remove-element/

    木又AI帮
  • 【leetcode刷题】T33-只出现一次的数字

    Given a non-empty array of integers, every element appears twice except for one....

    木又AI帮
  • 【leetcode刷题】T34-只出现一次的数字 II

    Given a non-empty array of integers, every element appears three times except fo...

    木又AI帮
  • LeetCode72|前K个高频元素

    hashMap键值对集合加上堆排序的使用,也算是堆,即优先级队列的使用吧,一般自己的写法都是很常规的写法,所以看懂java语法就知道怎么个意思了。

    码农王同学
  • LeetCode45|数组中重复的数据

    给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。

    码农王同学
  • LeetCode34|数组中的第k个最大元素

    请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

    码农王同学
  • leetcode 300. Longest Increasing Subsequence

    找到整数数组中最长的递增子数组。该子数组可以为不连续的。如题目中例子所示,[10, 9, 2, 5, 3, 7, 101, 18]得到的最长子数组为[2,3,7...

    眯眯眼的猫头鹰
  • BZOJ1278: 向量vector(计算几何 随机化乱搞)

    首先我们可以按极角排序。然后对\(y\)轴上方/下方的加起来分别求模长取个最大值。。

    attack
  • Leetcode: Rotate Array

    Rotate an array of n elements to the right by k steps.

    卡尔曼和玻尔兹曼谁曼
  • 最大堆,DP问题-LeetCode 373 374 376 377 605(DP,最大堆)

    给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。 定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums...

    算法工程师之路

扫码关注云+社区

领取腾讯云代金券