内容简介:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
题目
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 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; } }
热门阅读
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- leetcode136. 只出现一次数字
- LeetCode之只出现一次的数字-Swift
- 找出数组中第 k 大的数字及其出现次数
- LeetCode 137.只出现一次的数字 II
- [剑指offer题解][Java]数组中出现次数超过一半的数字
- LeetCode 136:只出现一次的数字 Single Number
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。