【6.4】位运算-判断是否存在重复元素

一、题目

二、解题思路

        这道题可以采用暴力求解的方法，即使用两个 for 循环进行每两两比较，不过这种方式的复杂度较高，这里就不给出具体代码了。除了暴力求解之外，其实还有一种方式，估计大家都能想到，那就是先对数组进行排序。排序之后，如果存在相同的元素，它们肯定是相邻的，然后我们再对排序后的数组进行前后两两比较即可。

        我们也可以使用 set 集合来解决这个问题。因为 set 集合中不能包含重复元素，如果有重复元素就会将其替换掉。我们把数组中的元素全部添加到集合 set 中，如果 set 的 size 与数组的长度不相等，那就说明存在重复的元素。

        我们主要探讨用位运算来解决此问题。这里要判断数组中是否有重复的数字，而判断是否有重复数字，最容易想到的一种解决方式就是使用位运算。c++中，long 类型在64位系统中占 64 位，每一位可以表示一个数字，所以一个 long 类型可以用来表示 64 个数字。但是要想在32位系统做到代码通用，可以使用64位整数类型表示 64 个数字。

        实现方式比较简单，我们遍历数组中的所有元素，查看对应的位置是否为 1，如果是 1，说明存在重复的元素，我们直接返回 true。否则，把数组中元素对应的位置变为 1。比如数组中有个元素是 3，我们就把上面第 3 个位置变为 1。

        原理比较简单，但数组中元素的值不可能都小于 64，所以我们需要分组。根据数组的范围每 64 分为一组。因为数组中还可能有负数存在，所以我们第一步先找出数组中的最大值和最小值。每个元素的位置需要减去最小值来确定。举个例子，比如数组元素为 [3，-10，65，30]，最小值是 -10，那么每个元素的位置就是 [13，0，75，40]。我们可以看到 0、13、40 都是小于 64 的，所以它们在第一组里面，而 75 在第二组里面。我们可以申请一个 uint64_t 类型的数组 bitmap，其中 bitmap [0] 相当于第一组，bitmap [1] 相当于第二组……

三、代码实现

#include <iostream>
#include <vector>
#include <cstdint> // 包含uint64_t类型

bool containsDuplicate(const std::vector<int>& nums) {
    // 找出数组中的最大值和最小值
    int min = nums[0];
    int max = min;
    for (int num : nums) {
        if (num < min) min = num;
        if (num > max) max = num;
    }
    
    // 计算数组中最大值和最小值的差值，目的是要确定位图的长度
    int distant = max - min + 1;
    int bitmapSize = (distant - 1) / 64 + 1;
    std::vector<uint64_t> bitmap(bitmapSize, 0);
    
    for (int num : nums) {
        // 根据当前数字到最小数字的长度，定位到当前数字在位图中的位置
        int tmp = num - min;
        if ((bitmap[tmp / 64] & (1ULL << (tmp % 64))) != 0)
            return true;
        
        // 如果不存在重复的数字，就把当前这个位置变为1
        bitmap[tmp / 64] |= 1ULL << (tmp % 64);
    }
    
    return false;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 1};
    std::cout << "Contains duplicate: " << (containsDuplicate(nums) ? "true" : "false") << std::endl;
    return 0;
}

        这里需要注意，在进行 1ULL << (tmp % 64)) 运算时，1 后面一定要加上大写的 ULL，表示这是64位的无符号长长整数类型，ULL后缀确保了常量的位宽为64位，不管在多少位系统下。如果不加的话，1 就会被视为 int 类型。当数字比较大的时候，结果就会出现错误。

原文地址：https://blog.csdn.net/linshantang/article/details/143738182

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！