首页 > 代码库 > 【LeetCode】Single Number II (3 solutions)

【LeetCode】Single Number II (3 solutions)

Single Number II

Given an array of integers, every element appears threetimes except for one. Find that single one.

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

 

解法一:开辟map记录次数

class Solution {public:    int singleNumber(int A[], int n) {        map<int, int> m;        for(int i = 0; i < n; i ++)        {            map<int, int>::iterator it = m.find(A[i]);            if(it == m.end())                m[A[i]] = 1;            else                m[A[i]] ++;        }        for(map<int, int>::iterator it = m.begin(); it != m.end(); it ++)        {            if(it->second != 3)                return it->first;        }    }};

 

解法二:先排序,再遍历找出孤异元素

class Solution {public:    int singleNumber(int A[], int n)     {        sort(A, A+n);        //note that at least 4 elements in A        if(A[0] != A[1])            return A[0];        if(A[n-1] != A[n-2])            return A[n-1];        for(int i = 1; i < n-1; i ++)        {            if(A[i] != A[i-1] && A[i] != A[i+1])                return A[i];        }    }};

 

解法三:位操作。不管非孤异元素重复多少次,这是通用做法。

对于右数第i位,如果孤异元素该位为0,则该位为1的元素总数为3的整数倍。

如果孤异元素该位为1,则该位为1的元素总数不为3的整数倍(也就是余1)。

换句话说,如果第i位为1的元素总数不为3的整数倍,则孤异数的第i位为1,否则为0.

(如果非孤异元素重复n次,则判断是否为n的整数倍)

class Solution {public:    int singleNumber(int A[], int n) {        int count;        int ind = 1;    //mask position        int result = 0;        while(ind)        {            count = 0;            for(int i = 0; i < n; i ++)            {                if(A[i] & ind)                    count ++;            }            if(count % 3)                result |= ind;  //position ind is 1            ind <<= 1;        }        return result;    }};

【LeetCode】Single Number II (3 solutions)