leetcode 645. 错误的集合

问题描述

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

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

示例 1:

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

输出: [2,3]

注意:

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

给定的数组是无序的。

代码1

首先给出一个利用hash表空间复杂度为O(N)的算法

class Solution {

public:

    vector<int> findErrorNums(vector<int>& nums) {

        int n = nums.size();

        map<int,int> tab;

        vector<int> ans(2,-1);

        for(int i = 0; i < n; i++)

            tab[i+1] = 0;//注意统计的数是从[1,n]

        for(int i = 0; i < n; i++)

            ++tab[nums[i]];//初始化hash表

        for(int i = 0; i < n; i++)

        {

            if(tab[i+1] == 0)ans[1] = i+1;

            if(tab[nums[i]] == 2)ans[0] = nums[i];

        }

        return ans;

    }

};

结果：

执行用时 :164 ms, 在所有 C++ 提交中击败了5.60%的用户

内存消耗 :34.2 MB, 在所有 C++ 提交中击败了5.47%的用户

或者使用vector来代替map

class Solution {

public:

    vector<int> findErrorNums(vector<int>& nums) {

        int n = nums.size();

        vector<int> tab(n,0);

        vector<int> ans(2,-1);

        for(int i = 0; i < n; i++)

            ++tab[nums[i]-1];//初始化hash表

        for(int i = 0; i < n; i++)

        {

            if(tab[i] == 0)ans[1] = i+1;

            if(tab[nums[i]-1] == 2)ans[0] = nums[i];

        }

        return ans;

    }

};

结果：

执行用时 :32 ms, 在所有 C++ 提交中击败了89.26%的用户

内存消耗 :23.2 MB, 在所有 C++ 提交中击败了5.47%的用户

代码2

再给出一个空间复杂度为O(1)的算法,以题目中例子为例：

我们第一遍遍历尝试将所有nums[i]-1所对应的 nums[abs(nums[i]-1)]变为负数，以表示该数已经存在了，如果nums[abs(nums[i]-1)]<0,代表元素nums[i]重复了。，遍历完以后，只有一个索引所对应的nums[i]为正的，这个索引就是缺失的值。

class Solution {

public:

    vector<int> findErrorNums(vector<int>& nums) {

        int n = nums.size();

        vector<int> ans(2,-1);

        for(int i = 0; i < n; i++)

        {

            int index = abs(nums[i]) - 1;

            if(nums[index] < 0)ans[0] = fabs(nums[i]);

            else nums[index] *= -1;

        }

        for(int i = 0; i < n; i++)

        {

            if(nums[i] > 0)ans[1] = i+1;

        }

        return ans;

    }

};

结果：

执行用时 :36 ms, 在所有 C++ 提交中击败了73.22%的用户

内存消耗 :22.7 MB, 在所有 C++ 提交中击败了5.47%的用户

巴特西

leetcode 645. 错误的集合

问题描述

代码1

代码2

最新文章

热门文章