交付：选型实现测量优化

👁️ 0 人浏览 💬 0 人评论 ❤️ 添加收藏

这是这条路线、也是整个数据结构领域的最终作品。选型表、慢版、benchmark 计数都已经写好，补全三个关键函数（dedup 快版、report、distinct），然后一次验完五条：choose 给出「集合加数组」且表外需求给出「还得再想想」；去重结果按首次出现是苹果/香蕉/梨；200 条时的对比数据是 19900/200/99；慢版和快版结果完全一致；三条边界都对。五条全过输出 验收通过，否则输出 验收失败。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 第四步：优化后行为不能变 std::list 边遍历边删 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

string choose(const string& need) {
    map<string, string> pick = {{"只要判重", "集合"}, {"判重还要保序", "集合加数组"}, {"只要前K大", "堆"}};
    auto it = pick.find(need);
    return it == pick.end() ? "还得再想想" : it->second;
}

vector<string> dedup(const vector<string>& words) {
    // TODO: 快版：集合判重、数组保序
    return {};
}

vector<string> slow_dedup(const vector<string>& words) {
    // 慢版：每次都在数组里从头找一遍
    vector<string> out;
    for (const string& w : words) {
        if (find(out.begin(), out.end(), w) == out.end()) out.push_back(w);
    }
    return out;
}

long long list_ops(int n) {
    // 数组判重：每加一条，都要和已经在里面的挨个比一次
    long long ops = 0;
    vector<int> seen;
    for (int i = 0; i < n; i++) {
        for (int y : seen) {
            (void)y;
            ops++;
        }
        seen.push_back(i);
    }
    return ops;
}

long long set_ops(int n) {
    // 集合判重：每条只算一次位置
    long long ops = 0;
    unordered_set<int> seen;
    for (int i = 0; i < n; i++) {
        ops++;
        seen.insert(i);
    }
    return ops;
}

string report(int n) {
    // TODO: 数组版次数/集合版次数/倍数
    return "";
}

int distinct(const vector<string>& words) {
    // TODO: 用 unordered_set 判重，返回不重复的个数
    return -1;
}

string join(const vector<string>& v) {
    string s;
    for (size_t i = 0; i < v.size(); i++) s += (i ? "/" : "") + v[i];
    return s;
}

int main() {
    vector<string> words = {"苹果", "香蕉", "苹果", "梨", "香蕉", "苹果"};
    vector<string> big;
    for (int i = 0; i < 10000; i++) big.push_back(to_string(i % 1000));
    vector<bool> checks;
    checks.push_back(choose("判重还要保序") == "集合加数组" && choose("排序去重") == "还得再想想");
    checks.push_back(join(dedup(words)) == "苹果/香蕉/梨");
    checks.push_back(report(200) == "19900/200/99");
    checks.push_back(slow_dedup(words) == dedup(words));
    checks.push_back(distinct({}) == 0 && distinct(vector<string>(5, "苹果")) == 1 && distinct(big) == 1000);
    bool ok = true;
    for (bool c : checks) ok = ok && c;
    cout << (ok ? "验收通过" : "验收失败") << endl;
}

本次输入：

输出：

👩‍🏫

AI

💬 题目评论

交付：选型实现测量优化

更多题目

全部评论