首页 > 代码库 > leetcode 刷题之路 84 Single Number II
leetcode 刷题之路 84 Single Number II
Given an array of integers, every element appears three times except for one. Find that single one.
给定一个包含n个整数的数组,除了一个数出现一次外所有的整数均出现三次,找出这个只出现一次的整数。
思路,根据数组构成的特点可知,数组中所有数的某一位上1的个数总和为3*n或者3*n+1。
当只出现一次的整数该位为0时,总和为3*n,当只出现一次的整数该位为1时,总和为3*n+1。
因此我们可以计算数组中所有整数的每一位上1的个数,然后进行取模运算就可以得出只出现一次的整数每一个位的值。
AC code:
class Solution { public: int singleNumber(int A[], int n) { int res=0,numof1=0; for(int i=0;i<8*sizeof(int);i++) { for(int j=0;j<n;j++) { if((A[j]&1<<i)!=0) numof1++; } if(numof1%3!=0) res|=1<<i; numof1=0; } return res; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。