在其他数字都出现K次的数组中找到只出现M次的数字

在其他数字都出现偶数次的数组中找到只出现奇数次的1个数字

题目描述

给定一个数组 arr,其中只有一个数字出现了奇数次,其他数字都出现了偶数次,找出这个数字。

思路

使用异或运算符。我们可以声明一个变量 x,用它去和数组中的每个元素做异或运算,由于 n ^ n = 0, n ^ 0 = n,那么那些出现偶数次的数字和自身异或,结果为0。最后x中存的就是数组中只出现奇数次次的数字。

代码

 

在其他数字都出现偶数次的数组中找到只出现奇数次的两个数字

题目描述

给定一个整数数组 arr,已知这个数组中有两个数字只在数组中出现了奇数次,而其他数字都出现了偶数次。找到这两个数字。

思路

我们首先声明两个变量 x 和 y,让它们的初始值为0。如果该数组中的 a 和 b 都出现了奇数次,那么用 x 和数组中的每个元素异或的最终结果是 x = a ^ b,这个数字不为 0,所以 x 肯定有一个 bit 位是不为 0 的,假设是第 k 位不为 0,那么 a 和 b 中肯定有一个的第 k 位是1,而另外一个的第 k 位是 0。接下来用 y 去和数组中第 k 位为 1 的那些元素来做异或运算,当遍历完成时 y 中的值就是 a 和 b 中的某一个,而 x ^ y 就是另外一个。

代码

 

在其他数字都出现K次的数组中找到只出现一次的一个数字

题目描述

给定一个整数数组 arr 和一个大于 1 的整数 k。已知 arr 中只有 1 个数出现了 1 次,其他的数字都出现了 k 次。找出这个出现了 1 次的数字。

思路

声明一个长度为32的整形数组 digit,将这个数组初始化为0。然后遍历数组,计算 arr 中的每一个数字的第i位相加的和,存放在 digit[i] 中。如果我们让 digit[i] 对 K 取模,那么 digit[i] % k 就是 arr 中只出现 1 次的数字第 i 位上的值。因此我们可以从 digit 数组中恢复出要找的那个数字。举个例子:

X,Y,Z 是数组中的三个数字,X 和 Z 都出现了3次,而 Y 只出现了1次。将这三个数第 P 位上的数字相加,得到3,3 % 3 =0,即是 Y 第 P 位上的数;将第 Q 位上的数字相加,得到4,4 % 3 = 1,即是 Y 第 Q 位上的数字。

代码

下面这种解法更加神奇:

具体解释可参看上面的链接。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据