【Offer】[56-2] 【数组中唯一只出现一次的数字】
2024-10-21 23:23:51
题目描述
在一个数组中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字
[牛客网刷题地址]无
思路分析
如果一个数字出现三次，那么它的二进制表示的每一位(0或者1)也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来，那么每一位的和都能被3整除。我们把数组中所有数字的二进制表示的每一位都加起来。如果某一位的和能被3整除，那么那个只出现一次的数字二进制表示中对应的那一位是0;否则就是1。
测试用例
- 功能测试：唯一只出现一次的数字分别是0、正数、负数;重复出现三次的数字分别是0、正数、负数。
Java代码
public class Offer056_02 {
public static void main(String[] args) {
test1();
test2();
test3();
}
public static int findNumberAppearingOnce(int[] array) {
return Solution1(array);
}
private static int Solution1(int[] array) {
if(array==null || array.length<=0) {
return -1;
}
int[] bitSum = new int[32];
for(int i=0;i<array.length;i++) {
int bitMask = 1;
for(int j=31;j>=0;j--) {//将每个数字的每一位存储到bitSum中，并且对应的位相加
int bit = array[i] & bitMask;
if(bit!=0) {
bitSum[j]+=1;
}
bitMask = bitMask<<1;
}
}
int result =0;
for(int i=0;i<32;i++) {
result = result<<1;
result += bitSum[i]%3;
}
return result;
}
private static void test1() {
int[] array = {1,1,1,4,5,4,4,2,2,2};
System.out.println(findNumberAppearingOnce(array));
}
private static void test2() {
}
private static void test3() {
}
}
代码链接
最新文章
- jQuery文件上传插件Uploadify（转）
- app后端设计(12)--图片的处理
- JS编写全选，复选按钮
- Android 短信的还原
- code blocks 如何实现一键代码格式化
- Microsoft JET Database Engine (0x80004005)
- toggleClass
- WINDOWS BITLOCK
- maven项目部署到Repository(Nexus)
- JavaScript动态加载资源【js|css】示例代码
- cygwin安装gcc/g++
- 【转载】tomcat+nginx+redis实现均衡负载、session共享(二)
- 动态规划-数位DPwindy
- 示例， linq分组
- java实现随机四则运算
- Alpha阶段敏捷冲刺（七）
- SQL ser 进行表中的插入操作时，变量字段名，导致报错时解决办法 ：动态SQL
- 用原生JS实现多张图片上传及预览功能（兼容IE8）
- MySql--学习成长过程
- springcloud10---feign-with-hystrix_factory