java - 数组操作 : HackerRank Questions : JAVA

Question

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

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

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in your array.

For example, the length of your array of zeros . Your list of queries is as follows:

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

Add the values of between the indices and inclusive:

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]

The largest value is after all operations are performed.

下面给出的是我的方法。

 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;
}

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

Test1 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(每秒)

注:如果搜索 video tutorial ，一定要看看 here 详细解释。