【手把手带你刷LeetCode】——02.出现1次和K次的数（位运算）
（）【前言】：Hello，铁汁们好，又见面咯。今天是LeetCode打卡第二天，很高兴能和你一起学习，咱们一起加油。
原题：出现1次与出现K次的数
题目描述：
给定一个长度为 n 的整型数组 arr 和一个整数 k(k>1) 。
已知 arr 中只有 1 个数出现一次，其他的数都出现 k 次。
请返回只出现了 1 次的数。
示例1：
-
输入：[5,4,1,1,5,1,5],3
-
返回值：4
示例2：
-
输入：[2,2,1],2
-
返回值：1
哈哈，看过我之前关于位运算博客的童鞋都知道这题讲过，忘了的同学可以先回顾一下，这里咱们介绍更为巧妙的方法。
蓝桥杯算法竞赛系列第一章——位运算的奇巧淫技及其实战_安然无虞的博客-CSDN博客
方法一：暴力求解
利用两层循环，遍历数组，统计每一个数出现次数，返回只出现一次的数。
代码执行：
-
/**
-
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
-
*
-
*
-
* @param arr int一维数组
-
* @param arrLen int arr数组长度
-
* @param k int
-
* @return int
-
*/
-
int foundOnceNumber(int* arr, int arrLen, int k ) {
-
// write code here
-
//暴力法
-
//二重循环，每遍历一个数，就统计这个数出现了几次
-
//int count = 0;//放在外面就错了
-
for(int i = 0; i < arrLen; i++)
-
{
-
int count = 0;
-
for(int j = 0; j < arrLen; j++)
-
{
-
-
if(arr[i] == arr[j]) {
-
count++;
-
}
-
}
-
if(1 == count) {
-
return arr[i];
-
}
-
}
-
return 0;
-
}
【敲黑板】：定义count时，要将它放到第一层循环里面，想想为什么，如果放到循环外边会怎么样？这里我就不解释咯，仔细看，理解它就行了，重在体会哈。
时间复杂度：O(n^2) 两重循环
空间复杂度：O(1)
方法二：位运算
题解：出现k次就不能仅仅只利用异或就能解决了，因为k(奇数)个相同的数异或还是得到其本身。但是可以采用位运算的思想，因为出现k(奇数)次的数字们每个位（0或者1）也是出现k(奇数)次，因此每一位（1/0）出现次数的和能够被k整除。所以如果把每个数的二进制表示的每一位都加起来，对于每一位的和，如果能被k整除，那对应那个只出现一次的数字的那一位就是0，否则对应的那一位是1
代码执行：
-
/**
-
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
-
* @param arr int一维数组
-
* @param arrLen int arr数组长度
-
* @param k int
-
* @return int
-
*/
-
int foundOnceNumber(int* arr, int arrLen, int k ) {
-
-
//对每个二进制位求和，如果某个二进制位不能被k整除，那么只出现一次的数在这个二进制位上是1
-
//定义一个数组保存每一位的和
-
int array[32] = {0};
-
for(int i = 0; i < 32; i++){//求每个二进制位的和
-
int sum = 0;
-
-
for(int j = 0; j < arrLen; j++){
-
sum = sum + ((arr[j] >> i) & 1);//同1相与，计算数组元素每一位上1的个数
-
}
-
array[i] = sum;
-
}
-
int res = 0;
-
for(int l = 0; l < 32; l++) {
-
if(array[l] % k != 0) {
-
res = res + (1 << l);
-
}
-
}
-
return res;
-
}
注意哦，里面的每一个变量都不是随便定义的，想一想为什么放在那个位置，是不是只能放在那个位置，如果放在别的位置会怎么样？
时间复杂度：O(N)
空间复杂度：O(1)
简化：上面的写法还是有点麻烦，感觉多了点什么，最下面的一层循环其实没有必要，也就是说没必要开辟一个数组去保存每一位上1出现的次数
改写代码：
-
int foundOnceNumber(int* arr, int arrLen, int k ) {
-
-
int result = 0;
-
for(int i = 0;i < 32;i++) {
-
int count = 0;
-
for(int j = 0; j < arrLen; j++) {
-
if(arr[j] & (1 << i)) {
-
count++;
-
}
-
}
-
if(count % k == 1){
-
result ^= (1<<i);
-
}
-
}
-
return result;
-
}
总结
-
今天是力扣打卡第二天，说实话，时间是真的紧，不过我一定会坚持下去的！
-
上面的一些方法是借鉴力扣大佬们的，我感觉好理解的都已经上传啦，和铁汁们一起进步！
-
加油加油，不负韶华哦！！
文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。
原文链接：bit-runout.blog.csdn.net/article/details/121070700
- 点赞
- 收藏
- 关注作者
评论（0）