首页 > 代码库 > [LeetCode] Single Number II 单独的数字之二
[LeetCode] 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?
这道题是之前那道单独的数字的延伸，那道题的解法就比较独特，是利用计算机按位储存数字的特性来做的，这道题就是除了一个单独的数字之外，数组中其他的数字都出现了三次，那么还是要利用位操作来解此题。我们可以建立一个32位的数字，来统计每一位上1出现的个数，我们知道如果某一位上为1的话，那么如果该整数出现了三次，对3去余为0，我们把每个数的对应位都加起来对3取余，最终剩下来的那个数就是单独的数字。代码如下：
class Solution {public: int singleNumber(int A[], int n) { int res = 0; int count[32]; for (int i = 0; i < 32; ++i) { count[i] = 0; for (int j = 0; j < n; ++j) { if ((A[j] >> i) & 1) count[i] = (count[i] + 1) % 3; } res |= (count[i] << i); } return res; }};
还有一种解法，思路很相似，用3个整数来表示INT的各位的出现次数情况，one表示出现了1次，two表示出现了2次。当出现3次的时候该位清零。最后答案就是one的值。
ones代表第ith 位只出现一次的掩码变量twos代表第ith 位只出现两次次的掩码变量threes代表第ith 位只出现三次的掩码变量
class Solution {public: int singleNumber(int A[], int n) { int one = 0, two = 0, three = 0; for (int i = 0; i < n; ++i) { two |= one & A[i]; one ^= A[i]; three = one & two; one &= ~three; two &= ~three; } return one; }};
[LeetCode] Single Number II 单独的数字之二
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。