做商城网站建设,公司门户网站及oa系统建设的请示,大连专业制作网站,建站网站平台【前言】本文以及之后的一些题解都会陆续整理到目录中#xff0c;若想了解全部题解整理#xff0c;请看这里#xff1a; 第0006页 寻找重复数 今天想讨论的一道题在 LeetCode 上评论也是颇为“不错”。有一说一#xff0c;是道好题#xff0c;不过我们还是得先理解了它才… 【前言】本文以及之后的一些题解都会陆续整理到目录中若想了解全部题解整理请看这里 第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] 进行二进制展开举个例子如下表所示 13422xy第 0 位11 0 0022第 1 位0101132第 2 位0010011 对于第 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 位为 1x 不变满足 xy。 2、如果被替换的数第 i 位为 0且 target 第 i 位为 1x 加一满足 xy。 3、如果被替换的数第 i 位为 1且 target 第 i 位为 0x 减一满足 x≤y。 4、如果被替换的数第 i 位为 0且 target 第 i 位为 0x 不变满足 x≤y。 总而言之在替换后如果 target 的第 i 位为 1那么始终满足 x y如果为 0那么每次替换后始终满足 x ≤ y。因此接下来我们只需要按照位次复原这个数就可以了。 【源码展示】 class Solution {
public:int findDuplicate(vectorint 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;}
};
