Leetcode: SingleNumber II
Leetcode: SingleNumber II
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-25 15:13:43
发布于 2019-01-25 15:13:43
题目：
Given an array of integers, every element appears three times except for one. Find that single one.
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
解答：（这是参照别人的答案一步步想通的）
方法一：
int 型数据共有32位，可以用32个变量存储 这n个元素中各个二进制位上1 出现的次数，最后在进行模3操作，如果为1，那说明这一位是要找元素二进制表示中为 1 的那一位。
int singleNumber(int A[], int n)
{
int bits[32] = {0};//一个整数32位
int result = 0;//记录结果
for (int i = 0; i < 32; i++)
{
for (int j = 0; j < n; j++)
{
//(A[j]>>i)&1的值为0或者1，表示第j个数字的第i位为0或者1
//将其结果相加便得到第i位为1的个数
bits[i] += (A[j]>>i)&1;
}
//将第i位的结果放到第i位上去
result |= (bits[i]%3)<<i;
}
return result;
}方法二：
利用3个变量分别保存各个二进制位上1出现1次、2次、3次的情况，最后只需返回出现1次的那个变量就行了。
int singleNumber(int A[], int n)
{
int one=0, two=0, three=0;
for(int i = 0; i< n; i++){
two |= one & A[i];
one ^= A[i];
three = one & two;
//每次将达到3的清零
one &= ~three;
two &= ~three;
}
return one;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014年10月21日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读