数组操作：HackerRank 问题：JAVA

Question

我正在从hackerrank做这个数组操作问题，它告诉我编译错误因超时而终止。

对于小阵列，我的方法非常有效。这个错误只发生在更大的数组值上。

这是问题链接。问题在这里

从一个 1 索引的零数组和一个操作列表开始，对于每个操作，向两个给定索引之间的每个数组元素添加一个值，包括两个给定索引。执行完所有操作后，返回数组中的最大值。

例如，您的 zeros 数组的长度。您的查询列表如下：

a b k
1 5 3
4 8 7
6 9 1

将索引和包含之间的值相加：

index -> 1 2 3  4  5 6 7 8 9 10
        [0,0,0, 0, 0,0,0,0,0, 0]
        [3,3,3, 3, 3,0,0,0,0, 0]
        [3,3,3,10,10,7,7,7,0, 0]
        [3,3,3,10,10,8,8,8,1, 0]

最大值是在所有操作执行之后。

下面给出的是我的方法。

 static long arrayManipulation(int n, int[][] queries) {
    long max = 0L;
    long[] arr = new long[n];
    for (int i = 0; i < n; i++) {
        arr[i] = 0L;
    }
    for (int i = 0; i < queries.length; i++) {
        int[] q = queries[i];
        int start = q[0] - 1;
        int end = q[1] - 1;
        int val = q[2];
        long tempMax = updateVal(start, end, val, arr);
        if (tempMax > max) {
           max = tempMax;
        }
    }
    return max;
 }



static long updateVal(int start, int end, int val, long[] arr) {
   long max = 0L;
   for (int i = start; i <= end; i++) {
       arr[i] = arr[i] + val;
       if (arr[i] > max) {
           max = arr[i];
       }
   }
   return max;
}

下面给出了一些不适用于我的代码的测试类。
测试1 的Test2 Test3的

请帮我解决这个问题。我搜索了很多基于java的答案。
但我无法理解他们。
这是我最后的手段。请帮忙。

在 Kanahiya 的回答后更新

    static long arrayManipulation(int n, int[][] queries) {
        long max = 0L;
        int a, b, k;
        int[] arr = new int[n + 2];
        for (int i = 0; i < queries.length; i++) {
            a = queries[i][0];
            b = queries[i][1];
            k = queries[i][2];

            for (int j = 0; j < arr.length; j++) {
                if (j >= a) {
                    arr[j] = arr[j] + k;
                }
                if (j > b) {
                    arr[j] = arr[j] - k;
                }
            }
        }
        Arrays.sort(arr);
        max = arr[arr.length - 1];
        return max;
    }

Answer 1

由于给定的时间限制，暴力解决方案在这里不起作用。这就是您会收到超时错误的原因。

所以你需要优化你的代码，这可以在前缀和数组的帮助下完成。

不是将 k 加到数组中从 a 到 b 范围内的所有元素，而是累积差异数组

每当我们在任何索引处添加任何内容到数组中并应用前缀和算法时，相同的元素将被添加到每个元素直到数组的末尾。

ex- n=5, m=1, a=2 b=5 k=5

    i     0.....1.....2.....3.....4.....5.....6   //take array of size N+2 to avoid index out of bound
  A[i]    0     0     0     0     0     0     0

将 k=5 添加到 a=2

A[a]=A[a]+k // 从应该添加 k 个元素的位置开始索引

     i    0.....1.....2.....3.....4.....5.....6 
   A[i]   0     0     5     0     0     0     0

现在应用前缀和算法

     i    0.....1.....2.....3.....4.....5.....6 
  A[i]    0     0     5     5     5     5     5

所以你可以看到 K=5 在应用前缀和之后添加到所有元素直到最后，但我们不必添加 k 到最后。因此，要消除这种影响，我们还必须在 b+1 索引后添加 -K，这样只有 [a,b] 范围内才会有 K 元素添加效果。

A[b+1]=A[b]-k // 在第 b 个索引之后去除先前添加的 k 个元素的影响。这就是为什么在初始数组中添加 -k 和 +k。

    i    0.....1.....2.....3.....4.....5.....6 
  A[i]   0     0     5     0     0     0    -5

现在应用前缀和数组

    i    0.....1.....2.....3.....4.....5.....6 
  A[i]   0     0     5     5     5     5     0

您现在可以看到 K=5 从 a=2 添加到 b=5，这是预期的。这里我们只为每个查询更新两个索引，因此复杂度为 O(1)。

现在在输入中应用相同的算法

         # 0.....1.....2.....3.....4.....5.....6    //taken array of size N+2 to avoid index out of bound
5 3      # 0     0     0     0     0     0     0
1 2 100  # 0    100    0   -100    0     0     0       
2 5 100  # 0    100   100  -100    0     0   -100
3 4 100  # 0    100   100    0     0  -100   -100

要计算最大前缀总和，请在取最大累积前缀的同时将差值数组累加到。

执行完所有操作后，现在应用前缀和数组

    i      0.....1.....2.....3.....4.....5.....6 
  A[i]     0     100   200  200   200   100    0

现在您可以遍历此数组以找到最大值为 200。遍历数组将花费 O(N) 时间，更新每个查询的两个索引将花费 O(1)* 查询次数 (m)

整体复杂度=O(N)+O(M) = O(N+M)

这意味着 = (10^7+10^5) 小于 10^8（每秒）

注意：如果搜索视频教程，您必须在此处查看详细说明。

Answer 2

首先，万一你没有意识到，Terminated due to timeout不是编译错误，这意味着你的实现太慢了。挑战不是对问题实施任何正确的解决方案。解决方案也必须是有效的。由于您的解决方案效率低下，因此由于速度太慢而无法处理大量输入。

由于查询的数量似乎比数组的长度小 2 个数量级（在您发布的 3 个测试用例中为 100K 与 10M），因此仅使用查询而不是实际更新数组会更有效.

我不会给你一个实现，但我会建议一个应该比你当前的实现更有效的算法。

我建议您按如下方式处理查询：

1. 将第一个查询添加到已处理查询列表中，该列表将包含具有不相交子数组范围的查询。此列表将按第一个数组索引排序（您将通过在适当位置添加新元素来保持排序）。

2. 对于尚未处理的每个查询，查找与其重叠的所有已处理查询（您可以使用二分搜索来提高性能）。

   • 以这样一种方式拆分当前查询，即每个结果查询要么完全包含在现有的已处理查询中，要么不包含在每个现有的已处理查询中。

   • 对于拆分中创建的每个查询：

     • 如果它们的范围等于现有已处理查询的范围，则将查询的值添加到已处理查询中。
     • 如果它们的范围不包含在任何现有的已处理查询中，则将该查询添加为新的已处理查询。
     • 如果它们的范围部分包含在现有的已处理查询中，则拆分已处理查询。

我不确定我的解释是否足够清楚。我将展示一个例子

1 5 3
4 8 7
6 9 1

输入：

将 1 5 3 添加到已处理查询列表中。

Process 4 8 7：有一个已处理的查询与它重叠 - 1 5 3。

将 4 8 7 拆分为两个子查询：4 5 7 和 6 8 7。

4 5 7 包含在 1 5 3 中，因此将 1 5 3 拆分为 1 3 3 和 4 5 3+7

6 8 7 不包含在任何已处理的查询中，因此按原样添加。

现在处理的查询是：

1 3 3
4 5 10
6 8 7

Process 6 9 1：有一个已处理的查询与其重叠：6 8 7。

将 6 9 1 拆分为两个子查询：6 8 1 和 9 9 1。

6 8 1 具有与 6 8 7 相同的范围，它将变成 6 8 7+1

9 9 1 不包含在任何已处理的查询中，因此按原样添加。

现在处理的查询是：

1 3 3
4 5 10
6 8 8
9 9 1

在处理查询时，您会跟踪最大处理的查询值，因此在处理完所有查询后，您知道最大值为 10。