泉州网站建设dreamnm,运城网站建设多少钱,中国十大it培训机构排名,效果图外包剑指 Offer 56 - I. 数组中数字出现的次数
难度#xff1a;middle\color{orange}{middle}middle 题目描述
一个整型数组 numsnumsnums 里除两个数字之外#xff0c;其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)#xff0c;空间复杂度…剑指 Offer 56 - I. 数组中数字出现的次数
难度middle\color{orange}{middle}middle 题目描述
一个整型数组 numsnumsnums 里除两个数字之外其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)空间复杂度是O(1)。
示例 1
输入nums [4,1,4,6]
输出[1,6] 或 [6,1]示例 2
输入nums [1,2,10,4,1,4,3,3]
输出[2,10] 或 [10,2]限制
2nums.length100002 nums.length 100002nums.length10000 算法
(位运算)
如果除了一个数字以外其他数字都出现了两次那么如何找到出现一次的数字
全员进行异或操作即可。考虑异或操作的性质对于两个操作数的每一位相同结果为 0不同结果为 1。那么在计算过程中成对出现的数字的所有位会两两抵消为 0最终得到的结果就是那个出现了一次的数字。
那么这一方法如何扩展到找出两个出现一次的数字呢
如果我们可以把所有数字分成两组使得
两个只出现一次的数字在不同的组中
相同的数字会被分到相同的组中。
那么对两个组分别进行异或操作即可得到答案的两个数字。这是解决这个问题的关键。
那么如何实现这样的分组呢
记这两个只出现了一次的数字为 a 和 b那么所有数字异或的结果就等于 a 和 b 异或的结果我们记为 x。如果我们把 x 写成二进制的形式 xkxk−1...x2x1x_kx_{k-1}...x_2x_1xkxk−1...x2x1其中 xi∈0,1x_i∈ {0,1}xi∈0,1我们考虑一下 xix_ixi 0 和 xix_ixi 1 的含义是什么它意味着如果我们把 a 和 b 写成二进制的形式aia_iai 和 bib_ibi 的关系 xix_ixi 1 表示 aia_iai 和 bib_ibi 不等xix_ixi 0 表示 aia_iai 和 bib_ibi 相等。假如我们任选一个不为 0 的 xix_ixi 按照第 i 位给原来的序列分组如果该位为 0 就分到第一组否则就分到第二组这样就能满足以上两个条件为什么呢
首先两个相同的数字的对应位都是相同的所以一个被分到了某一组另一个必然被分到这一组所以满足了条件 2。
这个方法在 xix_ixi 1 的时候 a 和 b 不被分在同一组因为 xix_ixi 1 表示 aia_iai 和 bib_ibi 不等根据这个方法的定义「如果该位为 0 就分到第一组否则就分到第二组」可以知道它们被分进了两组所以满足了条件 1。
在实际操作的过程中我们拿到序列的异或和 x 之后对于这个「位」是可以任取的只要它满足 xix_ixi 1。但是为了方便这里的代码选取的是「不为 0 的最低位」当然你也可以选择其他不为 0 的位置。
复杂度分析 时间复杂度O(n)O(n)O(n)其中 nnn 是数组的长度。 空间复杂度 : O(1)O(1)O(1)
C 代码
class Solution {
public:vectorint singleNumbers(vectorint nums) {int ret 0;// a or b resultfor (auto num : nums) {ret ^ num;}// search 1int div 1;while ((div ret) 0) div 1;int a 0, b 0;for (int n : nums) {if (div n)a ^ n;else b ^ n;}return vectorint{a, b};}
};
