首页 文章

因黑客等级“数组操作”超时而终止

提问于
浏览
-2

伙计们我想解决"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 回答

  • 2

    最优线性算法

    我自己想出了这个想法,我首先阅读了一些让我在线性时间内找出最优算法的东西 . 基本上,这个想法是在索引 a 处记录值 +k ,在每个查询处在索引 b 处记录值 -k . 然后,它允许您通过简单地计算数组的运行总和(从左侧开始)来计算 m 查询后每个单元格的总值 . 非常聪明,我'm sad it'不是我自己的想法!

    这是Scala的一个解决方案,我通过了所有HackerRank的测试:

    object Solution {
        def main(args: Array[String]) {
            val lines       = scala.io.Source.stdin.getLines()
            val Array(n, m) = lines.next().split(' ').map(_.toInt)
    
            val arr = Array.ofDim[Int](n)
    
            for (line <- lines) {
                val Array(low, high, k) = line.split(' ').map(_.toInt)
                arr(low  - 1) += k
                if (high < arr.length) arr(high) -= k
            }
    
            var runningSum = BigInt(0)
            var max = BigInt(0)
    
            for (i <- arr) {
                runningSum += i
                max = runningSum.max(max)
            }
    
            println(max)
        }
    }
    

    其他想法供参考

    我最初考虑使用可能在这里有用的数据结构 . 它被称为interval tree . 使用此数据结构,您可以以对数时间存储和查询一组间隔 .

    我的想法是,如果你设法将更新查询存储为与值相关的间隔(添加到间隔的每个元素的数量),你可以在 O(m log n + m) 中解决问题,这已经比天真的 O(m * n) 解决方案快得多,但仍然没有上述线性解决方案那么快 .

相关问题