leetcode260. Single Number III

Terry_Tai 发布于2019-08-15 14:19 / 259人阅读

摘要：要求我们找到这两个数字。举例解释一下第二个位运算一个数的负数是通过计算其正数的补码获得的。比如的八位二进制为，那么其反码为，再在反码上加一得到其补码也就是的二进制形式。从而获得二进制最右侧的位置。

题目要求

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

假设一个整数数组中，除了两个数字以外，所有的数字都出现了两遍。要求我们找到这两个数字。

可以先参考Single Number I 和 Single Number II。

思路与代码

这里需要了解两个位运算的重要知识：

a^b^b = a 即b^b=0
a&(-a)能够获得a的二进制形式的最右侧的1的位置。

举例解释一下第二个位运算：
一个数的负数是通过计算其正数的补码获得的。比如5的八位二进制为00000101，那么其反码为11111010，再在反码上加一得到其补码11111011也就是-5的二进制形式。
那么我们可以知道，一个数与其反码的与运算，得出的结果一定为0。而反码加一则代表着将原数的最后一位1在反码上也置为1。从而获得二进制最右侧1的位置。

    public int[] singleNumber(int[] nums) {
       int diff = 0;
        for(int num : nums){
            diff ^= num;
        }
        
        diff &= -diff;
        
        int[] result = {0, 0};
        for(int num : nums){
            if((num & diff) == 0){
                result[0] ^= num;
            }else{
                result[1] ^= num;
            }
        }
        return result; 
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 III single Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68535.html

[LintCode/LeetCode] Single Number III

摘要：去掉最后一个保留最后一个保留最后一个保留第一个这道题在论坛里参考了和两位仁兄的解法。思想是将中所有的数进行异或运算。不同的两个数异或的结果，一定至少有一位为。最后，将和存入数组，返回。 Problem Given 2*n + 2 numbers, every numbers occurs twice except two, find them. Example Given [1,2,2...

lanffy 2019-08-14 15:33 评论0 收藏0
由三道 LeetCode 题目简单了解一下位运算

摘要：使用位运算数组只出现一次数字的数组得到最低的有效位，即两个数不同的那一位看完上面的解法，我脑海中只有问号的存在，啥意思啊下面就让我们简单了解一下位运算并解析一下这三道题目。另，负数按补码形式参加按位与运算。你可做过这几道题？在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目： # 136. 只出现一次的数字给定一个非空整数数组，除了某个元素只出现一次以外...

daydream 2019-05-21 11:41 评论0 收藏0
由三道 LeetCode 题目简单了解一下位运算

摘要：简单介绍一下位运算异或运算异或逻辑的关系是当不同时，输出当相同时，输出。另，负数按补码形式参加按位与运算。使一个数的最低位为零，可以表示为。，截止到这儿，三道题目中使用的位运算介绍完毕，那么这里我们插入一下的详细题解。你可做过这几道题？在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目： # 136. 只出现一次的数字给定一个非空整数数组，除了某个元素只...

刘明 2019-05-22 14:21 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
[LeetCode] 557. Reverse Words in a String III

Problem Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. Example 1:Input: Lets take LeetCode contest...

104828720 2019-08-16 13:33 评论0 收藏0