【Leetcode】137.只出现一次的数字 II
【Leetcode】137.只出现一次的数字 II
Leetcode名企之路
发布于 2019-07-09 20:08:17
发布于 2019-07-09 20:08:17
题目
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99题解
根据上一道题目的经验，我们很明确的知道不能用数数字的办法去解。考虑位运算的办法，找相关的性质。
这个题其实就是求，在其他数都出现k次的数组中有一个数只出现一次，求出这个数。
而上面那个k次的是有通用解法的。
使用一个32维的数组，用这个32维的数组存储:
[第31位1的总数， 第30位1的个数，…， 第1位1的个数]
- 假如第0位1的个数是k的倍数，那么要求的这个数在该位一定是0；
- 若不是k的倍数，那么要求的这个数在该位一定是1。 因为假如说数组中的某些数在该位置是1，那么因为这个数要么出现k次，那么出现1次。
这样我们就可以找出只出现一次那个数的二进制表示形式。二进制如何转化为10进制呢？
假如，按照上面的规则，最招找到的二进制为:
A = [0, 0, 0, 0, 0, …, 1]
因为异或操作是：相同为0，不同为1。
那么久可以依次用 1, 2, 4, 8… 和依次每一位异或，即可得到最终答案。
第二部分可能不好理解，可以手动模拟下。
class Solution {
public int singleNumber(int[] nums) {
// 有多少个相同的数字
int N = 3;
// [高位1的个数,...,低位1的个数]
int[] bitNum = new int[32];
for (int i = 0; i < nums.length; i++) {
int compare = 1;
int num = nums[i];
for (int j = bitNum.length - 1; j >= 0; j--) {
if ((compare&num) != 0) {
bitNum[j]++;
}
compare = compare << 1;
}
}
int compare = 1;
int res = 0;
for(int i = bitNum.length - 1; i >= 0; i--) {
if(bitNum[i] % N != 0) {
res = res ^ compare;
}
}
return res;
}
}热门阅读
Leetcode名企之路
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-07-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
云数据库 Redis
腾讯云数据库 Redis（TencentDB for Redis）是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备，提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。