落单的数

题意

给出 2*n + 1 个的数字,除其中一个数字之外其他每个数字均出现两次,找到这个数字。

样例

给出[1,2,2,1,3,4,3],返回 4

思路

在位运算中,异或(^)是将该数的二进制每一位进行异或运算,当前位的两个二进制表示不同则为 1 ,相同则为 0。

根据此特性,可以得出结论:两个相同的数进行异或运算的结果为 0。

即:5 ^ 5 = 0,那么 5 ^ 5 ^ 6 的结果就是 6,这样就符合本题的要求了,6 就是那个 2n + 1 中的 1,即落单的数。

代码实现

public class Solution {
    /**
      *@param A : an integer array
      *return : a integer 
      */
    public int singleNumber(int[] A) {
        int r = 0;
        for (int i = 0; i < A.length; i++) {
            r ^= A[i];
        }
        
        return r;
    }
}

原题地址

LintCode:落单的数

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 落单的数Ⅲ

    一份执着✘
  • 爬楼梯

    一份执着✘
  • LeetCode 191 Number of 1 Bits

    这里用到了位运算, 如数字 5, 二进制位为 101, 那么使用 & 运算, 和 1 进行与运算, 如:

    一份执着✘
  • 数字科技:不是乌托邦,更不是独立王国

    人们对于数字科技的拥趸并不说他们真正明白数字科技是什么,而是因为他们看到了数字科技本身的基础性以及在数字科技身上所表现出来的互联网的影子。

    孟永辉
  • LeetCode 484. 寻找排列(找规律+贪心)

    现在给定一个只由字符 ‘D’ 和 ‘I’ 组成的 秘密签名。 ‘D’ 表示两个数字间的递减关系,‘I’ 表示两个数字间的递增关系。 并且 秘密签名 是由一个...

    Michael阿明
  • 判断无向图是否是一颗树

    DuncanZhou
  • QList的at与[]10亿次运行速度比较

    Qt君
  • 【LeetCode】11.盛最多水的容器

    给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai...

    Delevin
  • mysql中Timestamp,time,datetime 时间区别

    时间范围:1970-01-01 00:00:00——2037年。 适用场景:TIMESTAMP列用于INSERT或UPDATE操作时记录日期和时间。 表...

    瑞新
  • SystemVerilog覆盖率

    不是所有被覆盖的代码都会得到监测,由于没有得到足够的监测,因此一些即使被触发的漏洞也会在传播过程中没有到达监测点上。

    数字芯片社区

扫码关注云+社区

领取腾讯云代金券