leetcode137. Single Number II

mochixuan 发布于2019-08-15 11:12 / 915人阅读

摘要：按照思路一和思路二很容易将这题解决。在这里，我们希望将出现三次的数字通过操作划掉。之后，我们使用和分别来记录第一位和第二位的情况。最后只出现一次的数值应该是保存在中，换句话说，最后应该全是。

题目要求

Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

假设一个数组中只有一个数字只出现了一遍，其它数字都出现了三次。返回这个只出现了一次的数字。

思路和代码

在看下面的文章前，请先参考我的这篇文章关于Single Number I。按照思路一和思路二很容易将这题解决。下面要讲一个通过位计算来实现的方法。
在这里，我们希望将出现三次的数字通过%3操作划掉。比如将一个数字化为二进制数之后，在某一位上的数字为1，则1*3%3=0，如果在某一位上为0，则0*3%3=0。也就是说，出现三次的数值累加的情况应该是0->1->2->0。如果我们使用两位来表示也就是00->01->10->00(11)。之后，我们使用b0和b1分别来记录第一位和第二位的情况。然后我们逐位来看一下这两位之间的关联,就可以得出下面的式子。

b0 = b0 xor r & ~b1;

b1 = b1 xor r & ~b0;

最后只出现一次的数值应该是保存在b0中，换句话说，b1最后应该全是0。

    public int singleNumber(int[] A) {
        int ones = 0, twos = 0;
        for(int i = 0; i < A.length; i++){
            ones = (ones ^ A[i]) & ~twos;
            twos = (twos ^ A[i]) & ~ones;
        }
        return ones;
    }

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

服务器托管海外云主机 single Leetcod LeetCode single-spa

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

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

由三道 LeetCode 题目简单了解一下位运算

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

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

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

刘明 2019-05-22 14:21 评论0 收藏0
[LintCode/LeetCode] Single Number I & II [位运算]

摘要：整个过程相当于，直接在和里去掉既是又是的。所以最后返回的，一定是只出现过一次的，而出现两次的都在里，出现三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

Drinkey 2019-08-14 15:33 评论0 收藏0
[Leetcode] Single Number 单身数

摘要：最新思路解法请访问排序法复杂度时间空间思路先将数组排序，再遍历一遍，找前后都不一样的那个数即可。代码累加所有数中该位的个数位异或法复杂度时间空间思路我们用三个变量分别记录出现一次的数，出现两次的数和出现三次的数。 Single Number I 最新思路解法请访问：https://yanjia.me/zh/2018/11/... Given an array of integers,...

gecko23 2019-08-14 12:27 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0