leetcode15，leetcode-Single Number II-137

2023-10-18 阅读 32 评论 0

摘要：輸入一個數組，其中除了一個元素只出現一次外，其余元素都出現3次，找出只出現一次的元素一個系列http://www.cnblogs.com/0summer/p/5829973.html 位運算。出現3次的元素，二進制位上的0或1也必然有3次，以二進制位為劃分，求每個二進制

輸入一個數組，其中除了一個元素只出現一次外，其余元素都出現3次，找出只出現一次的元素

一個系列http://www.cnblogs.com/0summer/p/5829973.html

位運算。出現3次的元素，二進制位上的0或1也必然有3次，以二進制位為劃分，求每個二進制位中1出現的次數，%3得到的就是只出現一次的元素的該二進制位的數

時間：ONlgN，即32*N，空間：O32

注意：對于取二進制位來說，%2和&1在正數時等價，但在負數時不等價；判斷是否為奇數正負都等價

leetcode15、同理，n/=2和n>>=1也注意

 1 class Solution {
 2 public:
 3     int singleNumber(vector<int>& nums) {
 4         int len=nums.size();
 5         //if(len<3) return 0;
 6         int ans=0;
 7         int cnt[40];
 8         memset(cnt,0,sizeof(cnt));
 9         for(int i=0;i<32;i++){
10             for(int j=0;j<len;j++){
11                 cnt[i]+=(nums[j]>>i)&1;
12             }
13             ans|=(cnt[i]%3)<<i;
14         }
15         return ans;
16     }
17 };