简述:
虽然标题是这么描述的,但是我们不是一上来就解这道题,先看一下他的子题和扩展
子题:136. 只出现一次的数字 - 力扣(LeetCode)
扩展题:
所以我们由易到难,先来看第一道,只出现1次的数字,leetcode136
题目描述一:
解题思路一 :
Leetcode136 因为比较简单:就直接说了
在访问第 i 个数时,在不借助额外数据结构存储已访问的元素的情况下,我们无法判断当前访问的数有没有出现过。
那我们有没有方法通过某种运算让出现两次的数消失,最终的运算结果就是只出现一次的数。而位运算中的异或(XOR, 在Java中,用'^'表示) 可以。异或运算规则为:相同为 0,不同为 1。0 ^ 0 = 0; 1 ^ 1 = 0; 1 ^ 0 = 1;
让数组中的所有数异或,直接找到答案。
代码实现一:
//思路:所有数字异或 ^ 相同数字^为0,任何数字^0还是本身
public int singleNumber(int[] nums) {
int res = nums[0];
for(int i = 1; i < nums.length; i++) {
res ^= nums[i];
}
return res;
}
题目描述二:
解题思路二:
这道题有两种解法,如下:
方法一:借用哈希表,key为出现的数字,value为出现数字的次数,借助这么一个结构,最后再遍历哈希表,即可找到答案,显然空间复杂度O(n),时间复杂度O(n)
方法二:不用哈希表
我们前面说过,在访问第 i 个数时,在不借助额外数据结构存储已访问的元素的情况下,我们无法判断当前访问的数有没有出现过。既然无法将所有数的二进制位进行异或运算,那能否做其他的运算?比如说“加法运算”,统计数组中所有的数在某个二进制位出现的次数,如果有二进制位出现的次数不是K的整数倍,说明有其他没有出现K次的数的贡献,而该数只有一个,就是答案。
这里的k,就是Leetcode137中的3 显然空间复杂度O(1),时间复杂度O(n)
代码实现二 :
//美团要求:时间(n) 空间O(1) 意味着我们不能采用额外的数据结构来作答
public int singleNumber(int[] nums,int k) {
int res = 0;
//整数由32位二进制表示 一般int 为4byte 32bit
int numDigits = 32;
for(int i = 0 ; i < numDigits; i++) {
int count = 0;
for(int j = 0; j < nums.length; j++) {
//统计数组中所有元素,从右向左数第 i 位 二进制上1的个数,>> 为右移操作
//为什么还要 & 1? 清除前面 1 的个数,防止影响当前这一位,也就是第i位的结果
count += (nums[j] >> i & 1) ;
}
if(count % k == 1) {
//还原只出现1次的数 1 的分布, << 为左移
res |= (1 << i);
}
}
return res;
}
//这是Leetcode137的本题,上面为美团扩展的
public int singleNumber(int[] nums) {
int res = 0;
int numDigits = 32;
for(int i = 0 ; i < numDigits; i++) {
int count = 0;
for(int j = 0; j < nums.length; j++) {
//统计数组中所有元素,从右向左数第 i 位 二进制上1的个数,>> 为右移操作
//为什么还要 & 1? 清除前面 1 的个数,防止影响当前这一位,也就是第i位的结果
count += (nums[j] >> i & 1) ;
if(count % 3 == 1) {
//还原只出现1次的数 1 的分布, << 为左移
res |= (1 << i);
}
}
}
return res;
}
//使用哈希表
public int singleNumber(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
Integer value = entry.getValue();
if (value == 1) {
return entry.getKey();
}
}
return nums[0];
}
疑惑点 :
扩展题和Leetcode137 代码中,外面套了一层for循环,有些人可能会疑惑,为什么多了一层for,时间复杂度还是O(n)?
因为我的外面的for是固定的32次,只是比较大,但是是常数,所以说,就算拆开来看 也是 O(32) * O(n) = O(n),32这个常数可以省略,所以我们的时间复杂度还是O(n)