P4305 [JLOI2011]不重复数字
发布日期:2021-05-07 09:39:59 浏览次数:10 分类:精选文章

本文共 1898 字,大约阅读时间需要 6 分钟。

为了解决这个问题,我们需要去除给定数列中的重复项,只保留第一次出现的数。为了实现这一目标,我们可以使用哈希表来记录已经处理过的数,这样可以快速查找并避免重复记录。

方法思路

  • 读取输入数据:首先读取输入数据,包括多个测试用例。每个测试用例包含一个整数n和n个数。
  • 初始化数据结构:使用一个哈希表(如unordered_map)来记录已经处理过的数,键是数值,值是一个布尔标记,用于表示该数是否已经被处理过。
  • 遍历并处理数:遍历输入的数,对于每个数,检查它是否已经在哈希表中存在。如果不存在,则将其添加到结果列表中,并记录到哈希表中;如果已经存在,则跳过。
  • 输出结果:将处理后的结果列表按要求格式输出,两个数之间用空格隔开。
  • 这种方法的时间复杂度是O(n),空间复杂度也是O(n),其中n是输入数据的大小。这种方法高效且适用于处理大规模数据。

    解决代码

    #include 
    #include
    #include
    #include
    using namespace std;void readNumber(long long& x) { x = 0; char ch = ' '; while ((ch = getchar()) != '\0') { if (isdigit(ch)) { x = x * 10 + (ch - '0'); } else if (ch == '-') { x = -x; } else { break; } }}void writeNumber(long long x) { if (x < 0) { putchar('-'); x = -x; } if (x == 0) { putchar('0'); return; } while (x > 0) { putchar(x % 10 + '0'); x /= 10; }}int main() { long long t; readNumber(t); for (long long _ = 0; _ < t; ++_) { long long n; readNumber(n); long long* numbers = new long long[n]; for (long long i = 0; i < n; ++i) { long long num; readNumber(num); numbers[i] = num; } unordered_map
    seen; vector
    result; for (long long num : numbers) { if (seen.find(num) == seen.end()) { seen[num] = true; result.push_back(num); } } if (result.empty()) { cout << "" << endl; } else { ostringstream oss; for (size_t i = 0; i < result.size(); ++i) { if (i > 0) { oss << ' '; } writeNumber(result[i]); } cout << oss.str() << endl; } delete[] numbers; } return 0;}

    代码解释

  • 读取输入readNumber函数用于读取输入的数值,可以处理负数和多位数。
  • 写入输出writeNumber函数用于将数值转换为字符串并输出,处理负数和零的情况。
  • 主函数:读取测试用例数量,然后处理每个测试用例。使用哈希表记录已处理过的数,遍历输入数组,保留第一次出现的数。
  • 输出结果:将处理后的结果列表转换为字符串并输出。
  • 这个方法确保了高效处理和正确输出,适用于处理多个测试用例和大规模数据。

    上一篇:SSLOJ1225 银河英雄传说&P1196
    下一篇:P1102 A-B数对

    发表评论

    最新留言

    路过,博主的博客真漂亮。。
    [***.116.15.85]2025年04月06日 16时44分58秒