（）【前言】：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; }
总结
- 今天是力扣打卡第二天，说实话，时间是真的紧，不过我一定会坚持下去的！
- 上面的一些方法是借鉴力扣大佬们的，我感觉好理解的都已经上传啦，和铁汁们一起进步！
- 加油加油，不负韶华哦！！
