专栏首页Michael阿明学习之路程序员面试金典 - 面试题 17.19. 消失的两个数字(数学/位运算)

程序员面试金典 - 面试题 17.19. 消失的两个数字(数学/位运算)

1. 题目

给定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字。

你能在 O(N) 时间内只用 O(1) 的空间找到它们吗?

以任意顺序返回这两个数字均可。

示例 1:
输入: [1]
输出: [2,3]

示例 2:
输入: [2,3]
输出: [1,4]

提示:
nums.length <= 30000

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/missing-two-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

2.1 数学公式

1^2+2^2+3^2+4^2+....+n^2 = n*(n+1)*(2n+1)/6
1+2+...+n = n*(1+n)/2
class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size()+2, a, b;
        long sum = 0, squareSum = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            squareSum += nums[i]*nums[i];
        }
        squareSum = long(n)*(n+1)*(2*n+1)/6 - squareSum;
        sum = n*(n+1)/2 - sum;
        for(a = 1; a <= n; ++a)
        {
            if(2*a*(sum-a) == sum*sum - squareSum)
                break;
        }
        b = sum-a;
        return {a,b};
    }
};

72 ms 22.5 MB

2.2 常规解法

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> ans;
        int i, j;
        for(i = 1, j = 0; i <= nums.size()+2 && j < nums.size(); ++i)
        {
            if(nums[j] != i)
                ans.push_back(i);
            else
                j++;
            if(ans.size()==2)
                return ans;
        }
        if(ans.size()==1)
            ans.push_back(i);
        else if(ans.size()==0)
        {
            ans.push_back(i);
            ans.push_back(i+1);
        }
        return ans;
    }
};

116 ms 22.4 MB

2.3 位运算

  • 0 异或所有数,以及1-n的所有数,只出现1次的两个数的异或值得到了
  • 把上面异或值不为0的二进制位找到
  • 用这个位把 1到n 和数组里的数(2n-2 个),按照上面找出的二进制位,分成2组
  • 即得到出现1次的两个数
class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int XOR = 0, a = 0, b = 0, i;
        for(auto& n : nums) XOR ^= n;
        for(i = 1; i <= nums.size()+2; ++i) XOR ^= i;
        for(i = 0; i < 32; ++i)
            if(XOR&(1<<i))//a、b二进制不同的位
                break;// i为 a,b 不相同的二进制位
        for(auto& n : nums)
        {
            if((n>>i)&1)//分组
                a ^= n;
            else
                b ^= n;
        }
        for(int j = 1; j <= nums.size()+2; ++j)
        {
            if((j>>i)&1)
                a ^= j;
            else
                b ^= j;
        }
        return {a,b};
    }
};

80 ms 22.3 MB

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员面试金典 - 面试题 17.04. 消失的数字(数学/位运算)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/missing-number-lcci 著作权归领扣...

    Michael阿明
  • LeetCode 324. 摆动排序 II

    给定一个无序的数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

    Michael阿明
  • LeetCode 159. 至多包含两个不同字符的最长子串(滑动窗口)

    给定一个字符串 s ,找出 至多 包含两个不同字符的最长子串 t ,并返回该子串的长度。

    Michael阿明
  • 【每日一题】41. First Missing Positive

    Given an unsorted integer array, find the smallest missing positive integer.

    公众号-不为谁写的歌
  • Leetcode 41. First Missing Positive

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • Leetcode 581. Shortest Unsorted Continuous Subarray

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • andriod游戏音效

    同学们在玩游戏的时候应该都会发现游戏中会有两种形式来播放音乐 ,一般设置选项中会明确标明 设置游戏音乐 与设置游戏音效。 客观的分析一下这两种形式的音乐,游戏背...

    xiangzhihong
  • LeetCode 268. Missing Number

    方法一:求0到n的和,再减去nums数组的和,但是可能会超int 方法二:求0到n的异或值,在异或nums数组里的每个数字,不超int

    ShenduCC
  • LeetCode89|在排序数组中查找数字I

    这道题之前的用法竟然是使用键值对集合HashMap来做的,现在看有点大材小用吧,时间复杂度为O(n),空间复杂度为O(1)就可以了,这或许就是一点个人的思考吧,...

    码农王同学
  • 算法(六)二叉堆获取最小的k个数

    如果你有一个文件,里面包含20万行的整数,如何获取前k个最小的数?首先可以想到两个思路:

    一只羊

扫码关注云+社区

领取腾讯云代金券