前言
本文主要介紹如何使用位運(yùn)算從一堆數(shù)中尋找出現(xiàn)K次的數(shù)，這一堆數(shù)中有很多數(shù)出現(xiàn)了M次技俐，只有一個(gè)數(shù)出現(xiàn)了K次乘陪，并且K是小于M的，另外要求額外空間復(fù)雜度為O(1)雕擂，時(shí)間復(fù)雜度為O(n)啡邑，那么該如何尋找出這個(gè)數(shù)呢？
例如井赌，給出一個(gè)數(shù)組arr=[1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4]谤逼，K = 2贵扰，M = 3。在這個(gè)數(shù)組中流部，只有1這個(gè)元素出現(xiàn)了2次戚绕，其他的元素都出現(xiàn)了3次，現(xiàn)在要求使用位運(yùn)算把1這個(gè)元素找出來(lái)枝冀。
思路分析
要求額外空間復(fù)雜度為O(1)舞丛，也就是說(shuō)，我們只能創(chuàng)建有限的果漾、固定的幾個(gè)變量瓷马。
之前的幾個(gè)尋找元素的題目都用到了異或運(yùn)算來(lái)解決的，這個(gè)題目還能用異或運(yùn)算嗎跨晴？這個(gè)就不可以了欧聘，如果K是個(gè)偶數(shù)的話，用異或就直接給干廢了端盆。
我們知道怀骤，在Java中，int型的二進(jìn)制的長(zhǎng)度為32位焕妙。
如果把這個(gè)數(shù)組的所有元素都轉(zhuǎn)成二進(jìn)制蒋伦，然后把二進(jìn)制每個(gè)位置的數(shù)據(jù)相加，存放到一個(gè)長(zhǎng)度為32位的數(shù)組中呢焚鹊？
步驟
假如數(shù)組arr=[a,a,b,b,b,c,c,c,d,d,d]痕届，K = 2，M = 3末患，要找出a這個(gè)元素研叫。
先聲明一個(gè)32位長(zhǎng)度的數(shù)組tmp，里面的元素都默認(rèn)為0璧针。
循環(huán)遍歷數(shù)組嚷炉，并把數(shù)組中的每一個(gè)元素都轉(zhuǎn)為二進(jìn)制形式。
把每一個(gè)元素的二進(jìn)制的值都累加到第1步聲明的32位長(zhǎng)度的數(shù)組中探橱。
循環(huán)遍歷這個(gè)32位長(zhǎng)度的數(shù)組申屹，判斷數(shù)組中每個(gè)元素的數(shù)值和M的關(guān)系。
如果數(shù)組中的元素是M的整數(shù)倍隧膏，那么說(shuō)明這個(gè)位置是沒(méi)有a這個(gè)元素的哗讥。
循環(huán)arr數(shù)組過(guò)程如下：
第1個(gè)元素a的二進(jìn)制假設(shè)為01111，累加到tmp數(shù)組中為胞枕，01111杆煞。
第2個(gè)元素a的二進(jìn)制假設(shè)為01111，累加到tmp數(shù)組中為，02222索绪。
第3個(gè)元素b的二進(jìn)制假設(shè)為01000，累加到tmp數(shù)組中為贫悄，03222瑞驱。
第3個(gè)元素b的二進(jìn)制假設(shè)為01000，累加到tmp數(shù)組中為窄坦，04222唤反。
......
以此類(lèi)推，直到把所有的元素全部累加鸭津。
還原出現(xiàn)K次的數(shù)
tmp數(shù)組中的元素彤侍，假如為T(mén)，代表著arr數(shù)組中元素二進(jìn)制位為1數(shù)出現(xiàn)的次數(shù)逆趋，他可能出現(xiàn)這幾種組合：
T = 1 * K + 1 * M盏阶，所有元素在這個(gè)二進(jìn)制位都為1。
T = 0 * K + 1 * M闻书，只有出現(xiàn)M次的數(shù)名斟，二進(jìn)制位為1。
T = 0 * K + 0 * M魄眉，所有元素在這個(gè)二進(jìn)制位都為0砰盐。
T = 1 * K + 0 * M，只有出現(xiàn)K次的數(shù)坑律，二進(jìn)制位為1岩梳。
從上面4種情況來(lái)看，因?yàn)?K < M晃择，如果說(shuō)T對(duì)M進(jìn)行取模運(yùn)算冀值，取模為0的話，說(shuō)明這個(gè)位置出現(xiàn)K次這個(gè)數(shù)的二進(jìn)制位一定為0宫屠，否則為1池摧。
所以，讓tmp數(shù)組中的元素與M進(jìn)行取模運(yùn)算激况，就能識(shí)別出來(lái)出現(xiàn)K次的數(shù)的二進(jìn)制位是什么情況作彤，然后把二進(jìn)制轉(zhuǎn)成十進(jìn)制就可以了，或者直接與0進(jìn)行或運(yùn)算乌逐，也能得到結(jié)果竭讳。
代碼實(shí)現(xiàn)
經(jīng)過(guò)上面的分析，來(lái)看下代碼是如何實(shí)現(xiàn)的吧浙踢。
public class Code18_FindKTimes {
public static int findKTimes(int[] arr, int k, int m) {
int[] tmp = new int[32];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j <= 31; j++) {
tmp[j] += (arr[i] >> j) & 1;
}
}
int res = 0;
for (int i = 0; i < 32; i++) {
if (tmp[i] % m != 0) {
res |= (1 << i);
}
}
return res;
}
public static void main(String[] args) {
int[] arr = {11, 11, 11, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4};
int kNum = findKTimes(arr, 3, 4);
System.out.println(kNum);
}
}
復(fù)制代碼
運(yùn)行輸出結(jié)果為：11绢慢。
(arr[i] >> j) & 1代碼含義為判斷arr[i]元素在第j位置的值是0還是1。
總結(jié)
本文主要介紹如何使用位運(yùn)算從一堆數(shù)中尋找出現(xiàn)K次的數(shù)，利用了二進(jìn)制胰舆、或運(yùn)算骚露、以及題目中M次的邏輯關(guān)系。
如果你有更好的辦法缚窿，歡迎在評(píng)論區(qū)留言交流棘幸。
