伙计们我想解决"Arrays Manipulation" in hacker rank
是的
您将获得一个大小的列表(1索引),用零初始化 . 您必须对列表执行操作并输出列表中所有元素的最大值 . 对于每个操作,您将获得三个整数,并且您必须为从索引到(包括两者)的所有元素添加值 .
例如,考虑一个大小列表 . 初始列表将是= [,,],并且在执行update =之后,新列表将是= [,,] . 在这里,我们为索引2和3之间的元素添加了值30.注意列表的索引从1开始 .
我的解决方案是
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
List<Long> arr = new ArrayList<Long>(Collections.nCopies(n, new Long(0)));
int m = in.nextInt();
for(int a0 = 0; a0 < m; a0++){
int a = in.nextInt();
int b = in.nextInt();
int k = in.nextInt();
for(int i=a-1;i<=b-1;i++){
arr.set(i, arr.get(i)+k);
}
}
in.close();
System.out.println(Collections.max(arr));
}
}
任何帮助...为什么我得到“因超时终止”???
1 回答
最优线性算法
我自己想出了这个想法,我首先阅读了一些让我在线性时间内找出最优算法的东西 . 基本上,这个想法是在索引
a
处记录值+k
,在每个查询处在索引b
处记录值-k
. 然后,它允许您通过简单地计算数组的运行总和(从左侧开始)来计算m
查询后每个单元格的总值 . 非常聪明,我'm sad it'不是我自己的想法!这是Scala的一个解决方案,我通过了所有HackerRank的测试:
其他想法供参考
我最初考虑使用可能在这里有用的数据结构 . 它被称为interval tree . 使用此数据结构,您可以以对数时间存储和查询一组间隔 .
我的想法是,如果你设法将更新查询存储为与值相关的间隔(添加到间隔的每个元素的数量),你可以在
O(m log n + m)
中解决问题,这已经比天真的O(m * n)
解决方案快得多,但仍然没有上述线性解决方案那么快 .