LCR 120. 寻找文件副本 (opens new window)

题目：

设备中存有 n 个文件，文件 id 记于数组 documents。若文件 id 相同，则定义为该文件存在副本。请返回 任一存在 副本的文件 id。

示例：

示例 1：

输入：documents = [2, 5, 3, 0, 5, 0]
输出：0 或 5

提示：

• 0 ≤ documents[i] ≤ n-1
• 2 <= n <= 100000

解题：

方法一：哈希表

利用数据结构特点，容易想到使用哈希表（Map）记录数组的各个数字，当查找到重复数字则直接返回。

==注意：题目是返回任一，也就是返回其中一个就行==

算法流程：

1. 初始化： 新建 HashMap ，记为 hmap ；
2. 遍历数组 documents 中的每个数字 doc ：
   • 当 doc 在 hmap 中，说明重复，直接返回 doc；
   • 将 doc 添加至 hmap 中；
3. 返回 −1。本题中一定有重复数字，因此这里返回多少都可以。

class Solution {
public:
    int findRepeatDocument(vector<int>& documents) {
        unordered_map<int, bool> hmap;
        for(int doc: documents) {
          if(hmap[doc]) return doc;
          hmap[doc] = true;
        }
        return -1;
    }
};

复杂度分析：

• 时间复杂度 O(N) ： 遍历数组使用 O(N) ，HashMap 添加与查找元素皆为 O(1) 。
• 空间复杂度 O(N) ： HashMap 占用 O(N) 大小的额外空间。

可调试的代码：

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int findRepeatDocument(vector<int>& documents) {
        unordered_map<int, bool> hmap;
        for (int doc : documents) {
            if (hmap[doc]) return doc;
            hmap[doc] = true;
        }
        return -1;
    }
};

int main() {
    // 示例用法
    vector<int> documents = { 1, 2, 3, 1, 5, 2 }; // 包含文件 ID 1、2 的副本
    Solution solution;
    int duplicateID = solution.findRepeatDocument(documents);

    if (duplicateID != -1) {
        cout << "存在副本的文件 ID 是: " << duplicateID << endl;
    }
    else {
        cout << "未找到存在副本的文件 ID" << endl;
    }

    return 0;
}