首页 > 代码库 > leetCode: Single Number II [137]
leetCode: Single Number II [137]
【题目】
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
【题意】
给定一个整数以外,其中除了一个整数只出现一次以外,其他都整数都出现3次,找出那个出现一次的数要求线性复杂度,不适用额外的空间?
【思路】
模拟三进制运算three, two, one 分别表示当前是否已经出现了3个1, 2个1, 1个1
0 0 0 表示没有出现1
0 0 1 表示出现了1个1
0 1 0 表示出现了2个1
0 1 1 表示出现了3个1,这时我们需要把它转化成
1 0 0 也就是3进制计算的结果,我们得到three=1,然后把two和one清0
各位的迭代关系如下:
two = (one & A[i]) | two 已经出现了一个1,这次又出现了一个1 或者 这次出现的不是1,但是本来就已经有两个1了
one = one ^ A[i] 如果本来就有一个1了,这次又出现一个1,那么这我们需要向two进一位(也就是上一步,将two设成1),这是我们需要将one清为0
three = two & one 如果已经出现了3个1,则three为1,此时需要将two和one清0
【代码】
class Solution { public: int singleNumber(int A[], int n) { int one=0; int two=0; int three=0; for(int i=0; i<n; i++){ two= (one & A[i]) | two; one= one ^ A[i]; three = one & two; // three=1表示1已经出现了3此,two和one需要清空 two &= ~three; one &= ~three; } return one; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。