当前位置: 首页> 游戏> 手游 > 百度爱采购怎么优化排名_太原网页设计师招聘_网站推广的策略_数据查询网站

百度爱采购怎么优化排名_太原网页设计师招聘_网站推广的策略_数据查询网站

时间:2025/7/10 18:05:02来源:https://blog.csdn.net/hlyd520/article/details/144385646 浏览次数:0次
百度爱采购怎么优化排名_太原网页设计师招聘_网站推广的策略_数据查询网站

文章目录

    • 题目链接:
    • 题目描述:
    • 解法
    • C++ 算法代码:
    • 图解


题目链接:

面试题 17.19. 消失的两个数字


题目描述:

1dad7f8cb1ba96f8d539115e3c60785e


解法

6fa9d66ff148de786924a91402134119

a,b是缺失的两个数

  1. 将所有的数异或在一起,得到tmp=nums^(1~N)

    tmp=a^b

  2. 找到tmp中,比特位上为1的那一位。(因为ab是不一样的,所以异或后不为0tmp上肯定有一位上比特位为1

  3. 根据x位的不同,把nums1~N里面所有的数划分成两类异或

    一类是 第x 位为 1 的数,另一类是 第x 位为 0 的数。

    分别对这两类数进行异或操作,因为成对的数会抵消,所以最终分别得到两个缺失的数 ab


C++ 算法代码:

class Solution 
{public:vector<int> missingTwo(vector<int>& nums) {// 1. 将所有的数异或在一起int tmp = 0;for(auto x : nums) tmp ^= x;for(int i = 1; i <= nums.size() + 2; i++) tmp ^= i;// 2. 找出 a,b 中比特位不同的那一位int diff = 0;while(1){if(((tmp >> diff) & 1) == 1) break;else diff++;}// 3. 根据 diff 位的不同,将所有的数划分为两类来异或int a = 0, b = 0;for(int x : nums)if(((x >> diff) & 1) == 1) b ^= x;else a ^= x;for(int i = 1; i <= nums.size() + 2; i++)if(((i >> diff) & 1) == 1) b ^= i;else a ^= i;return {a, b};}
};

图解

例如:nums = [1, 2, 4, 5],缺失的两个数是 36

  1. 异或所有数:1 ^ 2 ^ 4 ^ 5 = 2

  2. 异或 162 ^ (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6) = 3 ^ 6 = 5

  3. 找到 x = 0

  4. 分组:

    x 位为 1 的数:1, 3, 5 异或结果为 3

    x 位为 0 的数:2, 4, 6 异或结果为 6

  5. 最终返回 {3, 6}

关键字:百度爱采购怎么优化排名_太原网页设计师招聘_网站推广的策略_数据查询网站

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: