作者:whisper
链接:https://www.proprogrammar.com/article/869
声明:请尊重原作者的劳动,如需转载请注明出处
在一个数组 nums
中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1:
输入:nums = [3,4,3,3] 输出:4
示例 2:
输入:nums = [9,1,7,9,7,9,7] 输出:1
难度:中等;标签:无;编程语言:JAVA
无,这题不会,看题解方法吧
public int singleNumber(int[] nums) {
int[] counts = new int[32];
for(int num : nums) {
for(int j = 0; j < 32; j++) {
counts[j] += num & 1;
num >>>= 1;
}
}
int res = 0, m = 3;
for(int i = 0; i < 32; i++) {
res <<= 1;
res |= counts[31 - i] % m;
}
return res;
}
用位运算,把每个数每一位上的0和1记录下来,模3,那些出现3次的就为0,剩下的0,1就是剩余的一个数的(可以找几个数算一下试试就理解了)
public int singleNumber(int[] nums) {
int ones = 0, twos = 0;
for(int num : nums){
ones = ones ^ num & ~twos;
twos = twos ^ num & ~ones;
}
return ones;
}
这个位运算不行的估计是看不懂的,我也看不懂,直接看题解吧
面试题56 - II. 数组中数字出现的次数 II(位运算 + 有限状态自动机,清晰图解)
并行位运算,看了原来的式子化简还能懂一些,直接上面的式子完全看不懂,这个原来不会的就算了吧,想不到的,另外所谓的有限状态自动机可以这样理解,就是没有进位等,每一位和其它位都没有关联,只与当前位有关,这样没有关联性,只考虑当前位,解题的难度就降低很多
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202205 | 1 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论