JS HackerRank Jesse and Cookies - проблема с кучей тайм-аутов

Question

Привет У меня есть следующий код для решения проблемы Hackerrank: Джесси и Cookies.Я бился над этим более трех часов, и я не мог найти решение JavaScript или подсказку для этой проблемы.Кажется, мой код работает, за исключением того, что время ожидания большого массива (входной размер> 1 миллиона) истекло.

Есть ли способ сделать мой код более эффективным (я думаю, что временная сложность находится между линейной иn log n).

Вы можете попытаться использовать этот вход (в верхней строке справа указывается 'k', а все строки, начинающиеся со строки 2, являются частью массива): https://hr -testcases-us-east-1.s3.amazonaws.com / 16183 / input20.txt? AWSAccessKeyId = AKIAJ4WZFDFQTZRGO3QA & Expires = 1545016628 & Подпись = 8DuPZfIaF4fPzhKSSatLFTy7B0F * 100% * 100% * 2% -процент * 100% * 2% -процент * 100% * 100% * 2% -позволить * 100% * тип 100% * 2% -позволить * 100% * тип 100% * 2% -позволить * 100% * тип 100% * 2% -процентный * 100% * тип-100% * 8% -позволить *Ссылка на проблему: https://www.hackerrank.com/challenges/jesse-and-cookies/problem

Мой код:

function cookies(k, A) {
  A.sort((a,b)=>a-b)
  let ops = 0;
  while (A[0] < k && A.length > 1) {
    ops++;
    let calc = (A[0] * 1) + (A[1] * 2);
    A.splice(0, 2);
    let inserted = false
    if (A.length === 0) { // when the array is empty after splice
      A.push(calc);
    } else {
      for (var i = 0; i < A.length && !inserted; i++) {
        if (A[A.length - 1] < calc) {
          A.push(calc)
          inserted = true
        } else if (A[i] >= calc) {
          A.splice(i, 0, calc);
          inserted = true
        }
      }
    }
  }
  if (A[0] < k) {
    ops = -1;
  }
  return ops;
}

Answer 1

Я решил это с помощью Java.Вы можете адаптироваться к Javascript.

Этот код не требует использования кучи.Он просто работает на том же массиве.Пройдены все тесты для меня.

static int cookies(int k, int[] arr) {
    /*
     * Write your code here.
     */
    Arrays.sort(arr);
    int i = 0,
        c = arr.length,
        i0 = 0,
        c0 = 0,
        op = 0;
    while( (arr[i]<k || arr[i0]<k) && (c0-i0 + c-i)>1 ) {
        int s1 = i0==c0 || arr[i]<=arr[i0] ? arr[i++] : arr[i0++], 
            s2 = i0==c0 || (i!=c && arr[i]<=arr[i0]) ? arr[i++] : arr[i0++];
        arr[c0++] = s1 + 2*s2;
        op++;
        if( i==c ) {
            i = i0;
            c = c0;
            c0 = i0;
        }
    }

    return c-i>1 || arr[i]>=k ? op : -1;
}

• Прежде всего массив сортировки.
• Для вновь вычисленных значений сохраните их в диапазоне массива [i0-c0], этот новый массивне требует сортировки, потому что она уже отсортирована.
• Когда массив [ic] достигает (i == c: true) конца, забудьте об этом и работайте над arr [i0-c0].