时间戳

首页 > 解决方案 > 如何减少此代码中的内存使用量？

c++ - 如何减少此代码中的内存使用量？

问题描述

完整的问题在这里https://www.interviewbit.com/problems/random-attendance/。如果我不允许在这里问这些问题，请告诉我。我认为我的解决方案是正确的，并且我得到了所提供示例的预期结果，但出现内存超出错误。

bool compare (string a, string b){
    return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}

vector<int> Solution::solve(int A, vector<int> &B) {
    vector <string> x;
    for(int i=0; i<A; i++){
        x.push_back(to_string(i+1));
    }
    sort(x.begin(), x.end(), compare);
    vector <int> ans;
    for(int i=0; i<B.size(); i++){
        ans.push_back(stoi(x[B[i]-1]));
    }
    return ans;
}

标签： c++

解决方案

我只想编写将 B[i] 转换为给定 A 的正确值的函数，可能使用从 A 派生的额外预处理数据，这将加速/简化计算。预处理后的数据应该是大约（log_10 A）个整数，即最多10或20个整数。不一定不是 A 刺痛。

当 A 很大时，您提出的解决方案会惨遭失败，但是可以为任何 A 编写以 O(B) 运行的代码（只要 A 是 int 或 long long，实际速度可能应该是 O(B log log A) 为任意大的 A)。

作为提示，我会给你一个例子。假设 A = 392,908。

我们有一些 B[0]，我们想确定它的索引。

第一个数字是什么？是1还是2？可能是3还是4？怎么能说出来。

事实上，正好有 111,111 个索引以 1 开头并且与 2 相同，而有 11,111 个索引以 4 开头（与 5、6、7、8、9 相同）。

而剩余数量（A - 2*111,111+6*11,111）用于数字 3。使用此信息不难确定 B[0] 索引中的第一个数字。

休息可以通过类似的程序确定。

推荐阅读