qidao123.com技术社区-IT企服评测·应用市场

标题: 【第0006页 · 数组】寻找重复数 [打印本页]

作者: 李优秀 时间: 2024-9-9 05:08
标题: 【第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;
}
};

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)