Минимальная общая сумма из K массивов после удаления части их суффикса

Опубликовано: 19 Сентября, 2022

Даны K (K > 2) массивов разного размера в двумерном списке arr[][] , где элементы в каждом массиве неотрицательны. Найдите минимальную общую сумму K массивов после удаления части суффикса (возможно, ни одного) из каждого массива.

Примеры:

Input: K = 3, 
arr = {{5, 2, 4}, 
          {1, 4, 1, 1}, 
          {2, 3}}
Output: 5
Explanation: 1st array: [5, 5+2, 5+2+4], = {5, 7, 11} remove suffix array [2, 4]
2nd array: [1, 1+4, 1+4+1, 1+4+1+1], = {1, 5, 6, 7} remove suffix array [1, 1]
3rd array: [2, 2+3 ], = {2, 5} don’t remove any thing
5 is the minimum common sum of given arrays after removing part of the suffix.

Input: K = 4
arr = {{5, 3}, 
          {1, 4}, 
          {3, 1}, 
          {9, 3, 1}}
Output: -1
Explanation: There is so common sum at all, therefore print -1. 

Подход: Решение задачи основано на сумме префиксов и хешировании. Используйте сумму префикса для всего массива и хешируйте значение суммы префикса на карте или в хеш-таблице. Теперь для первого массива сумм префиксов найдите минимальное значение, которое присутствует во всех массивах сумм префиксов, используя хеш-таблицу. Выполните шаги, указанные ниже, чтобы решить проблему:

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

Ниже приведена реализация описанного выше подхода.


Временная сложность: O(K * N), где N — максимальный размер массива.
Вспомогательное пространство: О (К * Н)

РЕКОМЕНДУЕМЫЕ СТАТЬИ