在大量数据中查找重复的两个数

在大量数据中查找重复的两个数

bitmap 方法

必须是：1-n 连续数字

    int findDuplicate_bitmap(vector<int> &nums)
    {
        std::cout << "findDuplicate_bitmap: " << std::endl;
        int idx, bit;
        int numOfBytes = (nums.size() - 1) / 8 + 1;
        char *bytes = new char[numOfBytes];
        memset(bytes, 0, numOfBytes * sizeof(char));
        for (int i = 0; i < nums.size(); ++i)
        {
            idx = nums[i] / 8, bit = nums[i] % 8;
            if (!(bytes[idx] & (1 << bit)))
                bytes[idx] |= (1 << bit);
            else
                return nums[i];
        }
        return -1;
    }

hash 方法

把数字作为hash 表的索引，可以是不连续数字

    int findDuplicate_hash(vector<int> &nums)
    {
        std::cout << "findDuplicate_hash: " << std::endl;
        unordered_map<int, int> count; // 创建哈希表
        int numsSize = nums.size();
        for (int i = 0; i < numsSize; i++)
        {
            if (count.find(nums[i]) != count.end())
            {                   // 如果该元素已经在哈希表中出现过
                return nums[i]; // 返回重复数字
            }
            else
            {
                // 否则，将该元素添加到哈希表中并增加计数器
                count[nums[i]]++;
            }
        }
        return -1; // 未找到重复数字，返回 -1 或其他特殊值
    }

main函数测试

int main(int argc, char **argv)
{
    std::vector<int> nums = {1,2,3,4,5,6,7,8,9,10,11,2,13,14};
    std::vector<int> nums2 = {1, 3, 4, 48, 421, 41, 84, 814, 5, 887, 5485, 35, 54, 5485};

    auto printFunc = [=](std::vector<int> &nums)
                    {
                        for (auto num : nums)
                        {
                            std::cout << num << " ";
                        }
                        std::cout << std::endl;
                    };


    printFunc(nums);
    int ret = findDuplicate_bitmap(nums);
    std::cout << "findDuplicate: " << ret<<std::endl;

    printFunc(nums2);
    int ret2 = findDuplicate_hash(nums2);
    std::cout << "findDuplicate: " << ret2<<std::endl;

    return 0;
}

输出：

1 2 3 4 5 6 7 8 9 10 11 2 13 14 
findDuplicate_bitmap: 
findDuplicate: 2

1 3 4 48 421 41 84 814 5 887 5485 35 54 5485 
findDuplicate_hash: 
findDuplicate: 5485