落单的数Ⅲ

题意

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

样例

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

思路

这道题用到了很多位运算的小技巧。

首先将数组中所有的数进行异或,最终的结果就是两个落单的数的异或值。

根据异或的规律:两值相同则为 0,不同则为 1。两者又是两个不同的数,所以最后异或的结果肯定不为 0.

然后取出异或值的二进制位中最低一个值为 1 的数。例如对于异或值:60(111100),取最低一个值为 1 的数,也就是:4 (100)。

然后将数组所有数与这个数进行与运算,将结果为 0 的数分为一组,非 0 的数分为另一组。由于上方异或得到的规律可得,两个落单的数,肯定在两个不同的组里。

在对这两组进行 落单的数 中的操作即可分别得到两个落单的数。

代码实现

public class Solution {
    /**
     * @param A : An integer array
     * @return : Two integers
     */
    public List<Integer> singleNumberIII(int[] A) {
        int xor = 0;
        
        // xor 代表的是落单的两个数的异或值
        for (int i = 0; i < A.length; i++) {
            xor ^= A[i];
        }
        
        //lastBit 代表的是 xor 的二进制位中最低一个值为 1 的数。
        int lastBit = xor - (xor & (xor - 1));
        int r1 = 0, r2 = 0;
        
        for (int i = 0 ; i < A.length; i++) {
            if ((lastBit & A[i]) == 0) {
                r1 ^= A[i];
            } else {
                r2 ^= A[i];
            }
        }
        List<Integer> list = new ArrayList<Integer>();
        list.add(r1);
        list.add(r2);
        return list;
    }
}

原题地址

LintCode:落单的数Ⅲ

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 落单的数

    一份执着✘
  • 爬楼梯

    一份执着✘
  • LeetCode 783 Minimum Distance Between BST Nodes

    这道题很像: Minimum Absolute Difference in BST, 解法甚至可以通用.

    一份执着✘
  • vue2.0学习-方法轮子(持续佛系更新)

    排序方法 sort() 在使用时附加方法,解决类似于这样的排序bug:23,3,35 function sortNumber(a,b){ retur...

    余生
  • kubernetes 中 Qos 的设计与实现

    QoS(Quality of Service) 即服务质量,QoS 是一种控制机制,它提供了针对不同用户或者不同数据流采用相应不同的优先级,或者是根据应用程序的...

    田飞雨
  • dstat

    官方对dstat的定义为:多功能系统资源统计生成工具( versatile tool for generating system resource statis...

    胡齐
  • 排序之简单排序

    在元素之间进行比较,而Java提供了一个接口Comparable就是用来定义排序规则的。

    silentcow
  • Python-排序-01-字典排序

    系统:Windows 7 语言版本:Anaconda3-4.3.0.1-Windows-x86_64 编辑器:pycharm-community-2016.3....

    zishendianxia
  • 被汽车耽误的隐形代工巨头比亚迪?

    今年以来科技能源股普遍大涨,比亚迪作为业内为数不多的优质标的,也坐上了市值飙升的快车道。近日比亚迪代工苹果的消息一经公布,就立即引起各方关注,消息公布首日比亚迪...

    刘旷
  • 计算机硬盘大小转换(B,KB,MB,GB,TB,PB之间的大小转换)

    java程序员在实际的开发中会遇到很多的单位换算问题。今天我给大家带来的是关于计算机硬盘大小的换算。多数情况下,一般要求b,kb,mb,gb,tb,pb之间的大...

    业余草

扫码关注云+社区

领取腾讯云代金券