找到出现次数为K次的数

假设有一个数组中出现了一堆数，其中一个数出现了 K次，其余的数出现了M次，其中K<M 且 M>1，要求找到数组中出现K次的数。

算法思想

下图M=3，K=2，3和2都出现3次，只有1出现2次。

我们将数组中的数的二进制每个位置的1使用等长的数组进行统计，统计完毕后让每个位置的总数模M如果不等于0则出现K次的数在该位置为1，使用该方式还原出现K次的数即可。

代码实现

func FindKTimesNum(arr []int, K, M int) int {
	if arr == nil || len(arr) == 0 { // 不存在出现K次数字的情况返回-1
		return -1
	}
	bitArr := make([]int, 64)
	for _, num := range arr {
		CountOneInBitArr(bitArr, num) // 统计每一个num对应位置的1
	}
	ans := GetAnsNumByKM(bitArr, K, M) // 还原出现K次数的数字，0时需要校验真是出现次数
	if ans !=0 {
		return ans
	}
	count := 0
	for _, num := range arr {
		if num == 0 {
			count++
		}
	}
	if count == K {
		return 0
	}
	return -1
}

func CountOneInBitArr(bitArr []int, num int) {
	var index uint = 0
	for index < 64 { // 遍历num的每一位，将为1的位置统计下来
		if (num>>index) & 1 != 0 {
			bitArr[index]++
		}
		index++
	}
}

func GetAnsNumByKM(bitArr []int, K, M int) int {
	ans := 0
	for i, v := range bitArr { // 遍历二进制数组，找到目标数字每一位二进制为1的位置
		if v%M != 0 {
			ans |= 1<<uint(i)
		}
	}
	return ans
}