Манипуляции с массивами: HackerRank Вопросы: JAVA

Question

Я делаю эту проблему манипулирования массивом из hackerrank, и она говорит мне, что ошибка компиляции Завершена из-за тайм-аута .

Для небольших массивов мой метод работает отлично. Эта ошибка возникает только при больших значениях массива.

Вот ссылка на вопрос. Вопрос здесь

Начиная с 1-индексированного массива нулей и списка операций, для каждой операции добавьте значение к каждому элементу массива между двумя указанными индексами, включительно,Как только все операции будут выполнены, верните максимальное значение в вашем массиве.

Например, длина вашего массива нулей.Ваш список запросов выглядит следующим образом:

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

Ниже приведены несколько тестовых классов, которые не работают с моим кодом. Test1 Test2 Test3

Пожалуйста, помогите мне разобраться в этом.Я искал много ответов на основе Java.Но я не мог их понять.Это мое последнее средство.Пожалуйста, помогите.

Обновлено после ответа Канахайи

    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 до конца. поэтому, чтобы свести на нет этот эффект, мы должны добавить -K также после индекса b + 1, чтобы только из диапазона [a, b] был добавлен эффект добавления элемента K.

A [b + 1] = A [b] -k //, чтобы удалить эффект ранее добавленного элемента k после b-го индекса. вот почему добавление -k в исходный массив вместе с + k.

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

Теперь примените префикс sum Array

    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

Чтобы вычислить максимальную сумму префикса, накапливайте массив разностей до ?, принимая максимальный накопленный префикс.

После выполнения всех операций теперь примените префикс sum Array

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

Теперь вы можете пройти через этот массив, чтобы найти максимум, равный 200. обход массива займет O (N) времени, а обновление двух индексов для каждого запроса займет O (1) * количество запросов (м)

общая сложность = O (N) + O (M) = O (N + M)

это означает = (10 ^ 7 + 10 ^ 5), что меньше 10 ^ 8 (в секунду)

Примечание: Если вы ищете видеоурок , вы должны проверить его здесь для подробного объяснения .

Answer 2

Прежде всего, если вы этого не понимаете, Terminated due to timeout не является ошибкой компиляции, это означает, что ваша реализация слишком медленная. Задача состоит не в том, чтобы реализовать какое-либо правильное решение проблемы. Решение также должно быть эффективным. Поскольку ваше решение неэффективно, оно терпит неудачу для больших входов из-за слишком медленного.

Так как количество запросов на 2 порядка меньше длины массива (100 К против 10 М в 3 тестовых примерах, которые вы опубликовали), было бы более эффективно работать только с запросами, а не на самом деле. обновление массива.

Я не собираюсь давать вам реализацию, но я предложу алгоритм, который должен быть более эффективным, чем ваша текущая реализация.

Я предлагаю вам обработать запросы следующим образом:

1. Добавить первый запрос в список обработанных запросов, который будет содержать запросы с непересекающимися диапазонами подмассива. Этот список будет отсортирован по индексу первого массива (вы сохраните его, добавив новые элементы в нужную позицию).

2. Для каждого еще не обработанного запроса найдите все обработанные запросы, которые перекрывают его (вы можете сделать это с помощью бинарного поиска для повышения производительности).

   • Разделить текущий запрос таким образом, чтобы каждый из полученных запросов либо полностью содержался в существующем обработанном запросе, либо не содержался в каждом существующем обработанном запросе.

   • Для каждого из запросов, созданных в разбиении:

     • если их диапазон равен диапазону существующего обработанного запроса, добавьте значение запроса к обработанному запросу.
     • Если их диапазон не содержится ни в одном из существующих обработанных запросов, добавьте этот запрос в качестве нового обработанного запроса.
     • Если их диапазон частично содержится в существующем обработанном запросе, разбить обработанный запрос.

Я не уверен, что мое объяснение достаточно ясно. Я покажу пример с

1 5 3
4 8 7
6 9 1

ввод:

Добавить 1 5 3 в список обработанных запросов.

Процесс 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

Процесс 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.