leetcode-217

Posted on Edited on In Views: Word count in article: 4.3k Reading time ≈ 8 mins.

LeetCode 217 题解

217 - Duplicate Nums，是一道求解列表里是否有重复数字的题目

乍一看用哈希或者排序算法都可以解决，是个非常简单的题目，但是在实际的速度上都没有达到最优，因此记录一下优化的过程

1. Hash

哈希算法的时间复杂度为O(N)O(N)，空间复杂度也为O(N)O(N)，第一遍简单用unordered_map写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> s;
    for (int x : nums) {
        // check if the number had appeared before
        if (s.count(x)) return true;
        s.insert(x);
    }
    return false;
}

//或者直接利用 insert 的特性
bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> s;
    s.reserve(nums.size());
    
    for (int x : nums) {
        // insert 返回 pair<iterator, bool>
        if (!s.insert(x).second) {
            return true;
        }
    }
    return false;
}

甚至如果不从中途退出，直接比较最终的结果的话，牺牲一点时间就能得到很"炫炮"的一行代码

1
2
3
bool containDuplicate(vector<int>& nums){
    return unordered_set<int>(nums.begin(),nums.end()).size() < nums.size();
}

直接利用cpp提供的unordered_map来写，虽然直观，但是并没有得到很好的结果，其原因是unordered_map的底层是由拉链法实现的。它的组成部分为：

  1. 桶数组（Bucket Array）：一段连续的内存空间，存储指向链表的指针
  2. 链表节点（Linked Nodes）：存储实际元素的节点，通过指针连接

因为是动态分配，所以它存在在堆上，可能占用的是不连续的内存，遍历的时候需要跳跃访存；同时当新元素出现的时候，需要进行一个扩容 (rehash)。而扩容的过程是重新分配一个更大的桶数组（和用数组实现堆/栈相似），并且释放旧的桶数组并重新组织链表。由此可以小小优化一下

1
2
3
4
5
6
7
8
9
10
bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> s;
    s.reserve(nums.size());  // 关键优化：预先分配足够空间
    
    for (int x : nums) {
        if (s.count(x)) return true;
        s.insert(x);  // 不会触发 rehash
    }
    return false;
}

2. Sort

先排序，之后查看相邻的元素是否相同即可

理论上来说根据不同的排序方法，时间复杂度为O(N+N)O(N +N)到O(Nlog⁡N+N)O(N\log N + N)不等，比使用hash要更慢，但是实际上测试下来都比unordered_map要慢，

核心因素可能是数组在内存中连续，CPU的L1/L2 Cache对于这种情况读取效率高

1
2
3
4
5
6
7
8
bool containsDuplicate(vector<int>& nums) {
    //使用内置的 sort （快排）
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size() - 1; ++i) {
        if (nums[i] == nums[i + 1]) return true;
    }
    return false;
}

发现排序更有效之后，再试试用一些非比较排序的方法来优化，比如基数排序（牺牲空间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

static const int speedup = []() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return false;

        // 基数排序需要一个辅助数组
        vector<int> buffer(n);
        int* src = nums.data();
        int* dst = buffer.data();

        // 针对 32 位整数进行两轮基数排序（每轮 16 位，即 65536 个桶）
        // 第一轮：处理低 16 位
        int count[65536];
        
        // 第一次 Pass
        // 清空计数器
        for (int i = 0; i < 65536; ++i) count[i] = 0;
        // 分拣，看每个“篮子”里对应要放多少数字
        for (int i = 0; i < n; ++i) {
            count[(unsigned short)(src[i] ^ 0x80000000)]++; // 偏移符号位处理负数（异或运算反转最高位，改变映射区域）
        }
        // 将 count 转换为 dst 中的 index
        for (int i = 1; i < 65536; ++i) count[i] += count[i - 1];
        // 搬运数据
        for (int i = n - 1; i >= 0; --i) {
            dst[--count[(unsigned short)(src[i] ^ 0x80000000)]] = src[i];
        }

        // 第二轮：处理高 16 位
        swap(src, dst);
        for (int i = 0; i < 65536; ++i) count[i] = 0;
        for (int i = 0; i < n; ++i) {
            count[(unsigned int)((unsigned int)(src[i] ^ 0x80000000) >> 16)]++;
        }
        for (int i = 1; i < 65536; ++i) count[i] += count[i - 1];
        for (int i = n - 1; i >= 0; --i) {
            dst[--count[(unsigned int)((unsigned int)(src[i] ^ 0x80000000) >> 16)]] = src[i];
        }

        // 最终检查相邻元素
        for (int i = 0; i < n - 1; ++i) {
            if (dst[i] == dst[i + 1]) return true;
        }

        return false;
    }
};

这是目前为止最快的版本，但是还是没有达到 leetcode 排行榜中的最快

3. Customized HASH

基数排序分为两部分进行了处理，并且每一步都包含了初始化和搬运这两个小循环，而 hash 理论上只要搬运一次数据。因此看看有没有更好的 hash 实现方式

之前使用的unordered_map的数据结构是有利于完成之后的查询的一种结构，但是这道题其实只需要存储这一步，因为 hash 的特性会在存储的时候计算出映射，所以这个时候就已经能检验是否重复了。这里尝试了一个简单的线性探测，因为不会涉及到取出这个元素，所以它本身的主聚类导致查找的性能损失的劣势不复存在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return false;

        // 1. 空间换时间：设定哈希表大小为 2 的幂次
        // 负载因子控制在 0.5 以下，极大减少探测冲突
        int hashSize = 1;
        while (hashSize < n * 2) hashSize <<= 1; 
        int mask = hashSize - 1;

        // 2. 使用原始连续数组，分配极快且缓存友好
        vector<int> hashTable(hashSize, INT_MIN); 

        for (int x : nums) {
            // 3. 计算哈希：简单的无符号映射 + 位运算取模
            unsigned int h = (unsigned int)x;
            int idx = h & mask;

            // 4. 线性探测：如果位置被占用，直接检查下一个
            while (hashTable[idx] != INT_MIN) {
                if (hashTable[idx] == x) return true; // 发现重复，立即退出（Early Exit）
                idx = (idx + 1) & mask; // 线性向后移动
            }
            // 5. 填入新值
            hashTable[idx] = x;
        }

        return false;
    }
};

几个细节：

  • hash表的大小：要是负载因子大于 0.5，就要开辟大于 2*n 的空间，同时要保证 hashsize 为2的幂次，便于后面 计算hash 的优化
  • 计算hash：线性探测需要对数字和 hashsize 进行一个取模的运算。而 mod 运算处理起来是一个除法，需要复杂的逻辑单元处理；而按位与&只是简单的位运算，在汇编的时候只是一个 AND指令，运算代价小

总结

最终线性探测方法胜出

另：数据结构的一些算法已经快忘光了