首页 > 代码库 > Single Number II
Single Number II
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?
思路：由于所有元素都出现了三次，只有一个元素出现了一次。通过统计输入序列在二进制表示的每个位上1出现的次数求解该题。对每一位上1累计出现的次数对3取余即可求解出只出现一次的数。使用位运算完成上述操作。
1 class Solution { 2 public: 3 int singleNumber(int A[], int n) { 4 if( n <= 0 ) { return 0; } 5 int one = A[0], two = 0; 6 for( int i = 1; i < n; ++i ) { 7 two |= one & A[i]; 8 one ^= A[i]; 9 int not_three = ~(two & one);10 two &= not_three;11 one &= not_three;12 }13 return one;14 }15 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。