本文主要是介绍【第0006页 · 数组】寻找重复数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【前言】本文以及之后的一些题解都会陆续整理到目录中,若想了解全部题解整理,请看这里:
第0006页 · 寻找重复数
今天想讨论的一道题在 LeetCode 上评论也是颇为“不错”。有一说一,是道好题,不过我们还是得先理解了它才算真正的好题。这里我们展示一种使用二进制的做法,希望能帮到你哟!
【寻找重复数】给定一个包含
n + 1
个整数的数组nums
,其数字都在[1, n]
范围内(包括1
和n
),可知至少存在一个重复的整数。现在假设nums
只有一个重复的整数,请返回这个重复的数。要求:你设计的解决方案必须不修改数组nums
且只用常量级O(1)
的额外空间。
示例1 示例2 示例3 输入:nums = [1, 3, 4, 2, 2] 输入:nums = [3, 1, 3, 4, 2] 输入:nums = [3, 3, 3, 3, 3] 输出:2 输出:3 输出:3
【解题分析】这道题目最难的地方莫过于它的要求:只能使用常量级的额外空间!既然不能用一般的方法,我们便另辟蹊径,对所有数 [1, n] 进行二进制展开,举个例子如下表所示:
1 3 4 2 2 x y 第 0 位 1 1 0
0 0 2 2 第 1 位 0 1 0 1 1 3 2 第 2 位 0 0 1 0 0 1 1 对于第 i 位,我们用 x 记录 nums 中所有数满足二进制形式下第 i 位是 1 的数量有多少。用 y 记录 1 ~ n 中所有数在二进制形式下第 i 位是 1 的数量应该有多少。
比如说,上表中第 0 位,nums 中的数有 2 个的二进制形式该位为 1,而 1 ~ 4 中该位为 1 的数有 2 个。
那么怎么找出重复的数呢?假设重复的数是 k,那么,对于 k 二进制展开后所有为 1 的数位必定会导致 x > y。
但是这个结论我们还是需要证明一下的。
【证明】
如果 nums 数组中 target 出现了 2 次,其余的数各出现了 1 次,那么如果 target 的第 i 位为 1,那么 nums 数组的第 i 位 1 的个数 x 恰好比 y 大了 1。如果 target 的第 i 位为 0,那么 x = y。
如果 nums 数组中 target 出现了 3 次及以上,那么必然有一些数不在 nums 数组中。这个时候就相当于我们用 target 替换了这些数,我们要考虑的就是这样的替换对 x 会产生什么影响:
1、如果被替换的数第 i 位为 1,且 target 第 i 位为 1:x 不变,满足 x>y。
2、如果被替换的数第 i 位为 0,且 target 第 i 位为 1:x 加一,满足 x>y。
3、如果被替换的数第 i 位为 1,且 target 第 i 位为 0:x 减一,满足 x≤y。
4、如果被替换的数第 i 位为 0,且 target 第 i 位为 0:x 不变,满足 x≤y。总而言之,在替换后,如果 target 的第 i 位为 1,那么始终满足 x > y;如果为 0,那么每次替换后始终满足 x ≤ y。因此,接下来我们只需要按照位次复原这个数就可以了。
【源码展示】
class Solution { public:int findDuplicate(vector<int>& nums) {int n = nums.size(), ans = 0;// 确定二进制下最高位是多少int bit_max = 31;while (!((n - 1) >> bit_max)) {bit_max -= 1;}for (int bit = 0; bit <= bit_max; bit++) {int x = 0, y = 0;for (int i = 0; i < n; ++i) {if (nums[i] & (1 << bit)) {x += 1;}if (i >= 1 && (i & (1 << bit))) {y += 1;}}if (x > y) {ans |= 1 << bit;}}return ans;} };
这篇关于【第0006页 · 数组】寻找重复数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!