好看怎么上传视频网站吗,百度关键词排名销售,温江做网站公司,企业产品微网站收费吗可以使用 位运算 来解决这道题目。使用位运算的一个核心思想是基于数字的二进制表示#xff0c;统计每一位上 1 的出现次数#xff0c;并与期望的出现次数做比较。通过这种方法#xff0c;可以推断出哪个数字重复。
class Solution {
public:int findDuplicate(vectori… 可以使用 位运算 来解决这道题目。使用位运算的一个核心思想是基于数字的二进制表示统计每一位上 1 的出现次数并与期望的出现次数做比较。通过这种方法可以推断出哪个数字重复。
class Solution {
public:int findDuplicate(vectorint nums) {int n nums.size() - 1; //这里注意是nums.size()-1因为size是n 1所以数字取值范围是 [1,n]int countNum 0; int expectedNum 0;int result 0;//遍历32位,题目n10^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, 说明重复数字在当前位的值为1if(countNum expectedNum) {result result | mask;}//countNum 0;//expectedNum 0;}return result;}
};解释
由于 nums 数组长度是 n 1所以它包含从 1 到 n 的数字且有一个重复数字。我们逐位检查每一个 bit从 0 到 31统计 nums 数组中哪些数字在该位上是 1接着统计从 1 到 n 的数字在该位上是 1 的个数。如果 nums 中在某个位上的 1 的个数多于从 1 到 n 的数字在该位上的 1 的个数说明重复的数字在该位上是 1。最终通过将这些结果合并使用按位或运算我们就能得到重复的数字。
优点
这种方法的时间复杂度为 O(n * log n)因为我们要遍历每个 bit 位而每次统计的复杂度为 O(n)。空间复杂度为 O(1)因为只使用了常量级的额外空间。
这是一个比较巧妙的位运算解法适用于这类寻找重复数的场景。
