Блог

Главная - Вопросы по программированию - Как бы я суммировал каждое число в каждом массиве друг с другом

Как бы я суммировал каждое число в каждом массиве друг с другом

#javascript

Вопрос:

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

 function getMoneySpent(keyboards, drives, b) {
  let purchase = [];
  let result = -1;

  for(let i = 0; i < keyboards.length; i  ) {
   for(let j = 0; j < drives.length; j  ) {
     if((keyboards[i]   drives[j]) <= b) {
      purchase.push(keyboards[i]   drives[j]);
       result = Math.max(...purchase);
      } 
    }
   }
   return resu<
}

console.log(getMoneySpent([4], [5], 5)); // Should return  -1
console.log(getMoneySpent([3, 1], [5, 2 ,8], 10)); //Should return  9
console.log(getMoneySpent([40, 50, 60], [5, 8, 12], 60)) // Should return  58

Я не знаю, как сделать это более эффективным.

Комментарии:

1. Я не понимаю, как входы соотносятся с их выходами. Не могли бы вы, пожалуйста, добавить объяснение этому?

2. Я не понял, что должен был делать ваш код, но, по крайней мере, вы дали название этой проблеме — хотя мне все равно пришлось ее искать.

Ответ №1:

Одно небольшое улучшение состояло бы в том, чтобы не иметь purchase массива, а вместо этого вызывать Math.max только текущий лучший результат и новый результат:

 function getMoneySpent(keyboards, drives, b) {
  let result = -1;

  for (let i = 0; i < keyboards.length; i  ) {
    for (let j = 0; j < drives.length; j  ) {
      const newResult = keyboards[i]   drives[j];
      if (newResult < b) {
        result = Math.max(result, newResult);
      }
    }
  }
  return resu<
}

console.log(getMoneySpent([4], [5], 5)); // Should return  -1
console.log(getMoneySpent([3, 1], [5, 2, 8], 10)); //Should return  9
console.log(getMoneySpent([40, 50, 60], [5, 8, 12], 60)) // Should return  58

Более сложный подход, который уменьшил бы вычислительную сложность, состоял бы в том, чтобы сначала отсортировать оба массива, а затем иметь индекс сравнения для обоих массивов, начиная с концов:

 xxxxxxxx
       ^
yyyyyy
     ^

Выберите один из массивов и уменьшайте индекс, пока не достигнете точки, в которой сумма будет ниже b :

 xxxxxxxx
       ^
yyyyyy
   ^

Затем уменьшите другой индекс, по возможности увеличивая текущий индекс, пока первый индекс снова не закончится:

 xxxxxxxx
   ^
yyyyyy
     ^

и возьмите самую большую комбинацию в пределах найденного предела при увеличении.

Этот подход был бы O(n log n) сложным из-за .sort s. (Мое getMoneySpent вышесказанное O(n ^ 2) )

Метки: