Leetcode 寻找重复数

可以使用 位运算 来解决这道题目。使用位运算的一个核心思想是基于数字的二进制表示，统计每一位上 1 的出现次数，并与期望的出现次数做比较。通过这种方法，可以推断出哪个数字重复。

class Solution {
public:int findDuplicate(vector<int>& nums) {int n = nums.size() - 1; //这里注意是nums.size()-1，因为size是n + 1，所以数字取值范围是 [1,n]int countNum = 0; int expectedNum = 0;int result = 0;//遍历32位,题目n<=10^5，所以最大数也足够用32位来表示了for(int bit = 0; bit < 32; ++bit) {//遍历每一位时，首先需要在循环初始将这两个计数器清零。或者在循环末尾处清零。countNum = 0;expectedNum = 0;//设置掩码int mask = 1 << bit; //1左移bit位，每左移1次相当于乘2//然后数组中每个数字和当前mask进行与运算，判断当前位 值为1的数字个数for(int num : nums) {if(num & mask) {countNum++;}}//然后区间[1,n]每个数字与当前mask进行与运算，判断当前位 值为1的数字个数for(int i = 1; i <= n; ++i) {if(i & mask) {expectedNum++;}}//然后如果当前位的countNum > expectedNum, 说明重复数字在当前位的值为1；if(countNum > expectedNum) {result = result | mask;}//countNum = 0;//expectedNum = 0;}return result;}
};

解释：

1. 由于 nums 数组长度是 n + 1，所以它包含从 1 到 n 的数字，且有一个重复数字。
2. 我们逐位检查每一个 bit（从 0 到 31），统计 nums 数组中哪些数字在该位上是 1，接着统计从 1 到 n 的数字在该位上是 1 的个数。
3. 如果 nums 中在某个位上的 1 的个数多于从 1 到 n 的数字在该位上的 1 的个数，说明重复的数字在该位上是 1。
4. 最终通过将这些结果合并（使用按位或运算），我们就能得到重复的数字。

优点：

• 这种方法的时间复杂度为 O(n * log n)，因为我们要遍历每个 bit 位，而每次统计的复杂度为 O(n)。
• 空间复杂度为 O(1)，因为只使用了常量级的额外空间。

这是一个比较巧妙的位运算解法，适用于这类寻找重复数的场景。