LeetCode 448.找到所有数组中消失的数字

内容纲要

这个题目名字有点怪,需要注意“所有”修饰最后的“数字”,而不是“数组”。

题目描述

给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

解法思路

解法一

将元素值作为下标,按照这个下标去对应的位置加负号。
最后没有被加负号的元素,其下标即“消失的数字”。

解法二

同解法一,只是将加负号变为加数组长度。
最后小于数据长度的元素,其下标即“消失的数字”。

解法三

将元素值作为下标,将该元素移动到下标的位置,除非该位置的元素和自己相等。
最后没有在自己位置的元素,其下标即为“消失”的数字。

示例:4,3,2,7,8,2,3,1

  • 第1个元素是
    • 4,和nums[3]=7交换:7,3,2,4,8,2,3,1
    • 7,和nums[6]=3交换:3,3,2,4,8,2,7,1
    • 3,和nums[2]=2交换:2,3,3,4,8,2,7,1
    • 2,和nums[1]=3交换:3,2,3,4,8,2,7,1
    • 3,无需和nums[2]=3交换
  • 第2个元素是
    • 2,当前位置即nums[1],无需交换
  • 第3个元素是
    • 3,和nums[2]=3无需交换
  • 第4个元素是
    • 4,和nums[3]=4无需交换
  • 第5个元素是
    • 8,和nums[7]=1交换:3,2,3,4,1,2,7,8
    • 1,和nums[0]=3交换:1,2,4,3,3,2,7,8
    • 3,和nums[2]=4交换:1,2,3,3,4,2,7,8
    • 4,和nums[3]=3交换:1,2,3,4,3,2,7,8
    • 3,和nums[2]=3无需交换
  • 第6个元素是
    -2,和nums[1]=2无需交换
  • 第7个元素和第8个元素也无需交换

结果:1,2,3,4,3,2,7,8

nums[4]!=4+1
nums[5]!=5+1

所以5和6是消失的数字。

代码示例

vector<int> findDisappearedNumbers(vector<int>& nums) { // 解法一
        vector<int> res;

        for (int i = 0; i < nums.size(); ++i) {
            int index = abs(nums[i]) - 1;
            nums[index] = -abs(nums[index]);
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0)
                res.push_back(i+1);
        }

        return res;
    }

    vector<int> findDisappearedNumbers2(vector<int>& nums) { // 解法二
        vector<int> res;

        for (int i = 0; i < nums.size(); ++i) {
            int index = (nums[i] - 1) % nums.size();
            nums[index] += nums.size();
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] <= nums.size())
                res.push_back(i + 1);
        }

        return res;
    }

    void swap(vector<int>& nums, int index1, int index2) {
        if (index1 == index2)
            return;

        nums[index1] = nums[index1] ^ nums[index2];
        nums[index2] = nums[index1] ^ nums[index2];
        nums[index1] = nums[index1] ^ nums[index2];
    }

    vector<int> findDisappearedNumbers3(vector<int>& nums) { // 解法三
        vector<int> res;

        for (int i = 0; i < nums.size(); ++i) {
            while (nums[i] != nums[nums[i] - 1])
                swap(nums, i, nums[i] - 1);
        }

        for (int i = 0; i < nums.size(); ++i)
            if (nums[i] != i + 1)
                res.push_back(i + 1);

        return res;
    }

发表评论

电子邮件地址不会被公开。 必填项已用*标注

微信扫一扫

微信扫一扫

微信扫一扫,分享到朋友圈

LeetCode 448.找到所有数组中消失的数字
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close