LeetCode 137：Single Number II

本文主要是介绍LeetCode 137：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?

Single Number II 比Single Number要复杂的多，很难直观的找到算法。

考虑每个元素的为一个32位的二进制数，这样每一位上出现要么为1 ，要么为0。对数组，统计每一位上1 出现的次数count，必定是3N或者3N+1 次。让count对3取模，能够获得到那个只出现1次的元素该位是0还是1。

代码如下：

class Solution {
public:int singleNumber(vector<int>& nums) {int length = nums.size();int result = 0;for(int i = 0; i<32; i++){int count = 0; int mask = 1<< i;for(int j=0; j<length; j++){if(nums[j] & mask)count++;}if(count %3)result |= mask;}return result;}
};

该方法同样适用于Single Number I的解答。

class Solution {
public:int singleNumber(vector<int>& nums) {int length = nums.size();int result = 0;for(int i = 0; i<32; i++){int count = 0;int mask = 1<< i;for(int j=0; j<length; j++){if(nums[j] & mask)count++;}if(count %2)result |= mask;}return result;}
};

对于Single Number II，网上还有一种与、异或等位操作的解法，尚未完全理解，先记录下

int singleNumber(int A[], int n)
{int one = 0, two = 0;for (int i = 0; i < n; i++){two |= A[i] & one;one ^= A[i];int three = one & two;one &= ~three;two &= ~three;}return one;
}

这篇关于LeetCode 137：Single Number II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---