首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【Leetcode】26.只出现一次的数字III(位运算)

【Leetcode】26.只出现一次的数字III(位运算)

作者头像
FishWang
发布2025-08-27 13:14:56
发布2025-08-27 13:14:56
6700
代码可运行
举报
运行总次数:0
代码可运行

题目链接

点击打开链接

题目描述

在这里插入图片描述
在这里插入图片描述

题解

两个位运算
  1. 异或: 两个相同的数异或结果为0;0和任意值异或结果为那个数。
  2. x&(-x): 结果为x的二进制位的最后一位。 举个例子(第一位为符号位): 10 -> (0 00000…000 1010)b -10 -> (1 11111…111 0110)b 负数的二进制变换方式是:1. 按位取反。 2. 末位加1。 这时两个数进行与运算,结果就是 (0 0000.0000 10)b。
解题思路
  1. 所有数做异或运算,这时得到的结果表示:x和y的异或的结果(设x和y为结果,其它的数在异或的时候出现了2次,变成了0)。结果也可以理解为二进制位上为1的位置,就是x和y不同的位置,这个二进制位上,要么x为1,要么y为1。
  2. 对这个二进制位上为1的数再求一遍异或。就可以得到其中的一个数。
  3. 把得到的这个数和第1步求得的异或求异或,就得到了第2个数。
代码
代码语言:javascript
代码运行次数:0
运行
复制
/*
 * @lc app=leetcode.cn id=260 lang=cpp
 *
 * [260] 只出现一次的数字 III
 */

// @lc code=start
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int diff = 0;
        for (int n: nums)
            diff ^= n;
        int bit = diff&(-diff);  // 取二进制最后一个1
        
        int x = 0;
        for (int n: nums)
        {
            if (n&bit)  // 这一位为1
                x ^= n;
        }
        return {x, diff^x};
    }
};

我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=5260qmuycmh3

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-08-14,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目链接
  • 题目描述
  • 题解
    • 两个位运算
    • 解题思路
    • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档