137. 只出现一次的数字 II
2024-09-05 17:39:12
2021-04-30 LeetCode每日一题
链接:https://leetcode-cn.com/problems/single-number-ii/
方法1:使用map记录每个数出现的次数,再找出出现一次的数即可。
时间复杂度O(n),空间复杂度O(n)
class Solution {
int res = 0;
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
map.forEach((key, value) -> {
if (value == 1) {
res = key;
}
});
return res;
}
}
方法2:每位数转换为32位的二进制,使用一个长度为 32 的数组 cnt[]记录下所有数值的每一位共出现了多少次 1,再对 cnt[]数组的每一位进行 mod 3 操作,重新拼凑出只出现一次的数值。
考虑样例 [1,1,1,3],1和 3 对应的二进制表示分别是 00…001 和 00…011,存入 cnt[] 数组后得到 [0,0,…,0,1,4]。进行 mod3 操作后得到 [0,0,…,0,1,1],再转为十进制数字即可得「只出现一次」的答案 3。
时间复杂度O(n),空间复杂度O(1)
class Solution {
public int singleNumber(int[] nums) {
int[] count = new int[32];
int len = nums.length, res = 0;
for (int i = 0; i < len; i++) {
for (int j = 0; j < 32; j++) {
if (((nums[i] >> j) & 1) == 1) {
count[j]++;
}
}
}
for (int i = 0; i < 32; i++) {
if (count[i] % 3 == 1) {
res += (1 << i);
}
}
return res;
}
}
最新文章
- [LeetCode] Maximum Product of Word Lengths 单词长度的最大积
- InstallShield Limited Edition for Visual Studio 2013 图文教程
- MY SQL8.0里程碑发布
- [转]jQuery Popup Login and Contact Form
- js优化提升访问速度
- IIS设置允许下载.exe文件解决方法(转)
- HDU 4196 Remoteland
- Qt之模型/视图(自定义按钮)(使用QStyleOption的子类进行drawControl,和我用的方法完全不一样)
- 最近用的到的一些js的常用方法(简单的)
- ActiveReports 9 新功能:创新的设计分层报告
- Android应用--简、美音乐播放器获取专辑图片(自定义列表适配器)
- angularJS简单调用接口,实现数组页面打印
- 最近提交一个mysql5.7的bug,提醒自己以后注意写SQL要规范
- [Swift]枚举类型:UIBarButtonItem的24种样式
- vue3版本到vue2版本的桥接工具
- 微信小程序开发3之保存数据及页面跳转
- Android样式的开发:selector篇
- hadoop在zookeeper上的高可用HA
- MODIS 数据产品预处理
- [USACO10OPEN]牛跳房子Cow Hopscotch