[LeetCode] Single Number II 位运算
2024-08-29 22:38:21
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?
Hide Tags
数组中的数均出现3次,只有1个出现一次,可以参考http://www.cnblogs.com/Azhu/articles/3956568.html 说的。
[解题思路]
k为奇数时,如果k 大于10,就不用转换为2进制了,全部的数的同一位叠加(个位上的数叠加,十位上的叠加,百位上的....),mod k 之后结果放回对应位,便是目标int。
如果k <10,将数组中的数转换成2进制,全部数的同一位叠加,后mod k,得到的结果按位的位置还原成目标int。
#include <iostream>
using namespace std; class Solution {
public:
int singleNumber(int A[], int n) {
int cnt[]={};
int ret =;
for(int i=;i<n;i++){
int curnum = A[i];
while(curnum){
int idx= __builtin_ffs (curnum);
// cout<<idx<<endl;
cnt[idx]++;
curnum &=curnum-;
}
}
// for(int i=1;i<=32;i++)
// cout<<cnt[i]<<" ";
// cout<<endl;
int a=;
for(int i=;i<=;i++){
ret +=a*(cnt[i]%);
a=a<<;
}
return ret;
}
}; int main()
{
int a[]={,,,};
Solution sol;
cout<<sol.singleNumber(a,sizeof(a)/sizeof(int))<<endl;
return ;
}
discuss 中有一种使用内存更少的,
https://oj.leetcode.com/discuss/6632/challenge-me-thx
public int singleNumber(int[] A) {
int ones = , twos = ;
for(int i = ; i < A.length; i++){
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
}
return ones;
}
直观上难理解,只是思路是一样的,转换为二进制,然后每个位上面的数统计,然后mod(3),考虑1位,那么他的变化是
0 -> 1 ->2 -> 0
二进制就是:
00 -> 01 -> 10 -> 00
好了,这样只要两位就可以表示了,代码中的ones twos ,就这这个意思。
最新文章
- HTML5标签与HTML4标签的区别示例介绍_html5教程技巧
- C#操作注册服务卸载服务启动服务停止服务.. .
- Java面试题汇总(一)
- Java开发环境的配置
- ubuntu下libjson-c库的使用问题备忘
- 自定义view组件
- JAVA学习第五十九课 — 网络编程概述
- Vue 旅游网首页开发2 - 首页编写
- SpringBoot学习(七)-->;SpringBoot在web开发中的配置
- python自动化开发-[第十九天]-分页,cookie,session
- Delphi 如何操作Excel
- IIC通讯协议(非原创,转载他人,用于学习)
- python 压缩文件为zip后删除原文件
- Android:Unable to find explicit activity class
- Oracle空查询删除
- 大数据:Parquet文件存储格式【转】
- Java加密和C#解密=>;DES方法
- Oracle和MySQL的对比
- MUI框架-13-使用百度地图 API(图文教程)
- js获取来源网址