剑指 Offer 56 - II. 数组中数字出现的次数 II
题目详情
解题思路
java代码
package com.walegarrett.offer;
/**
* @Author WaleGarrett
* @Date 2021/2/10 13:43
*/
/**
* 题目描述：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
*/
public class Offer_56_2 {
public int singleNumber(int[] nums) {
int[] counts = new int[32];
for(int num : nums){
for(int i=0; i<32; i++){
counts[i] += (num&1);
num >>>=1;//>>>表示无符号右移
}
}
int ans=0, m=3;
for(int i=0; i<32; i++){
ans <<= 1;
ans |= (counts[31-i] % m);
}
return ans;
}
}
复杂度分析
- 时间复杂度 O(N) ： 其中 N 位数组 nums 的长度；遍历数组占用 O(N) ，每轮中的常数个位运算操作占用 O(1) 。
- 空间复杂度 O(1) ： 数组 counts 长度恒为 32 ，占用常数大小的额外空间。