首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >HackerRank -数组操作

问HackerRank -数组操作
EN

Code Review用户
提问于 2018-01-17 15:04:13
回答 1查看 5.2K关注 0票数 5

这是我对这个黑客级别问题的实现。(还有后续行动。)

问题

您将得到大小为n的列表(1-索引),该列表以零初始化。您必须对列表执行m个操作,并输出列表中所有元素的最大值。对于每个操作,给出三个整数a、b和,并且必须将值k添加到从索引到(都包括在内)的所有元素。

Example输入

代码语言:javascript
复制
5 3
1 2 100
2 5 100
3 4 100

Expected输出

代码语言:javascript
复制
200

解释

第一次更新后的列表将是:

代码语言:javascript
复制
100 100 0 0 0

第二次更新后的列表如下:

代码语言:javascript
复制
100 200 100 100 100

在第三次更新之后,将:

代码语言:javascript
复制
100 200 200 200 100

因此,所需的答案是: 200

First解决方案

我的第一次尝试,我认为是相当可读的(忽略输入和输出的方式处理黑客级别)

代码语言:javascript
复制
#include 
#include 

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector v(n);
    for(int a0 = 0; a0 < m; a0++){
        int start, end, val;
        cin >> start >> end >> val;
        auto it_start = v.begin()+(start-1);
        auto it_end = v.begin()+(end);
        transform(it_start, it_end , it_start, [k](long long &x){return x+=k;});
    }
    cout << *max_element(v.begin(),v.end());
    return 0;
}

Final解决方案

但是,这种方法虽然可读性强,但对于它实际要求的内容来说太慢了,这是它将达到的最大价值。所以我写了这个,它通过了测试,但在我看来更难理解。

代码语言:javascript
复制
#include 
#include 
#include 

int main() {
    int n; int m;
    std::cin >> n >> m;
    using val_type = long long;
    std::vector v(n);
    while(m--){
        val_type start, end, val;
        std::cin >> start >> end >> val;
        auto it_start = v.begin()+(start-1);
        auto it_end   = v.begin()+ end;
        *it_start     += val;
        *it_end       -= val;
    }
    val_type max{0};
    auto accumulate_max_val = [x=val_type(0),&max](val_type y) mutable{x+=y; if (x>max) max=x;};
    std::for_each(v.begin(),v.end(),accumulate_max_val);
    std::cout << max;
    return 0;
}

你会做些什么来改进它?我是适当地使用lambdas和for_each,还是有一种更清晰的方式来表达我想要做的事情?

EN

回答 1

Code Review用户

回答已采纳

发布于 2018-01-17 20:48:16

  • 因为知道正确的算法而受到赞扬。但是,您可以通过不使用v向量来简化它:正确地将操作a, b, k作为一对操作:将k从a添加到末尾,将k从b+1减到末尾。现在,不再将它们存储在v中,而是将解耦的操作收集到自己的向量中。按索引排序。std::partial_sum,并在结果数组中找到最大值。这将把空间复杂度从\O(N)降到\O( m)\$,并将时间复杂度从\O(n+m)\$改为\O(m\log m)\$。根据约束条件,时间复杂度似乎更好。您还应该记住,对v的访问可能在没有特定顺序的地方到处都是,精心编制的操作序列可能会导致太多的缓存丢失。不过我没有侧写。
  • 拼写出循环(而不是使用for_each和lambda)可能会提高可读性。
  • 如果允许k为负值,则该算法将失败。即使情况并非如此,将max和x初始化为v[0]并在v.begin() + 1启动循环仍然是一个好习惯。
票数 4
EN
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://codereview.stackexchange.com/questions/185320

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档