Single Number II leetcode java
2024-08-26 08:01:08
问题描述:
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?
提示:bit manipulation(位操作)
参考:http://www.acmerblog.com/leetcode-single-number-ii-5394.html?utm_source=tuicool&utm_medium=referral
分析:由于所有数字都是出现奇数次,所以,并不是简单的异或运算。
考虑所有数字用二进制表示,如果把第i个位置上所有数字的和对3取余,那么只会有两种结果,0或1。因此,取余的结果就是那个single number。
java 代码:
一、一个直接的实现就是用大小为 32的数组来记录所有位上的和。
public int singleNumber(int[] nums){ //所有数字都使用32位二进制表示,初始为0
int[] count = new int[32];
int result = 0; //singlenumber
for(int i = 0; i < 32; i++){
for(int j = 0; j < nums.length; j++){
int key = (nums[j] >> i) & 1;
if (key == 1) { //右移,获得第i个bit,统计1的个数
count[i] ++ ;
}
}
//第i位左移,然后将所有位相或,最终得到singlenumber
result |= ((count[i] % 3) << i);
}
return result;
}
二、使用掩码,改进算法一
ones
代表第ith 位只出现一次的掩码变量twos
代表第ith 位只出现两次的掩码变量threes
代表第ith 位只出现三次的掩码变量
public int singleNumber(int[] nums){ int ones = 0, twos = 0, threes = 0; for(int i = 0; i < nums.length; i++){ twos = twos | ( ones & nums[i]); ones = ones ^ nums[i]; //异或3次 和 异或 1次的结果是一样的 threes = ones & twos; //对于ones 和 twos, 把出现了3次的位置设置为0 (取反之后1的位置为0) ones = ones & ~threes; twos = twos & ~threes; } return ones; }
最新文章
- WPF资源使用
- Ubuntu安装图形桌面
- FileItem类 用法详解
- Public and Private Interfaces in ruby
- 自定义ContentProvider
- 只要把鼠标移上Div方框,方框就自动顺时针旋转
- AMD和CMD的区别
- dp中表示无限取的写法
- PHP判断变量是否为空的几种方法小结
- 【源码】HashMap源码及线程非安全分析
- 四、PyQt5布局管理(绝对&;相对、水平、垂直、格栅、表单)
- scrapy 中 xpath 用string方法提取带有空格符解决方法
- WORLD 合并多个WORLD中的文本
- 295B - Greg and Graph (floyd逆序处理)
- 小程序 showModal content换行
- kbmMW 5.08.01压力测试报告
- django 静态文件
- 麻省理工大学新发明:暗黑WiFi透视技术
- (转载)从Java角度理解Angular之入门篇:npm, yarn, Angular CLI
- python核心编程笔记——Chapter8
热门文章
- WSL及Linux入门
- C# 控制台运行 应用运行
- BZOJ 3622 已经没有什么好怕的了
- (转)Paper list of Meta Learning/ Learning to Learn/ One Shot Learning/ Lifelong Learning
- Even Odds (java)
- entity framework浅谈
- kubernetes 实战2_命令_Configure Pods and Containers
- 【NOIP 2016】Day1 T2 天天爱跑步
- linux 基本命令2(12月27日笔记)
- CIKM 18 | 蚂蚁金服论文:基于异构图神经网络的恶意账户识别方法