【前言】：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;
}總結
-
今天是力扣打卡第二天，說實話，時間是真的緊，不過我一定會堅持下去的！
-
上面的一些方法是借鑒力扣大佬們的，我感覺好理解的都已經上傳啦，和鐵汁們一起進步！
-
加油加油，不負韶華哦！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/344154.html
標籤：其他