首页 > 代码库 > LeetCode:Single Number II

LeetCode:Single Number II

2024-07-13 05:25:12   232人阅读

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?

 

这道题仍然用位运算来做，不过要比那道只用位异或来做的题要复杂得多。还是从数的二进制表示看起，假设数组大小为n，每个数由32位组成，分别把这n个数的第i位相加，然后%3，结果非0即1，结果为0时single one对应的位为0，结果为1时single one对应的位为1，最后返回32位的结果。

 

 1 class Solution { 2 public: 3     int singleNumber(int A[],int n){ 4         int bit=0,temp,i,j; 5         if(n<0) 6         { 7             return -1; 8         } 9         for(i=0;i<32;i++)10         {11             temp=0;12             for(j=0;j<n;j++)13             {14                 temp+=((A[j]>>i)&1);15             }16             bit|=((temp%3)<<i);17         }18         return bit;19     }20 };


联系
我们