Ошибка тайм-аута алгоритма пропущенного номера (JavaScript) - PullRequest
Новая
       22

Ошибка тайм-аута алгоритма пропущенного номера (JavaScript)

0 голосов
/ 07 сентября 2018

Я работаю над Codewars Kata, который проходит все тесты, кроме времени ожидания. Кто-нибудь может дать совет, как это оптимизировать? Заранее спасибо! Вот разбивка вопроса -

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

Найдите пропущенное число с повторяющимися номерами (дубликаты должны быть выведены в отсортированном массиве).

Давайте рассмотрим пример:

обр = = [10,9,8,9,6,1,2,4,3,2,5,5,3]

find_dups_miss ([10,9,8,9,6,1,2,4,3,2,5,5,3]) == [7, [2,3,5,9]]

А вот мое решение - 

function findDupsMiss(arr) {
  let missingNum = [];
  let newArr = [];
  arr = arr.sort((a, b) => a - b);
  let dup = [...new Set(arr)];
  for (let y = 1; y < dup.length; y++) {
    if (dup[y] - dup[y - 1] != 1) missingNum.push(dup[y] - 1)
  } 
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) newArr.push(arr[i])
    }
  }
  missingNum.push(newArr);
  return missingNum;
}

1 Ответ

0 голосов
/ 07 сентября 2018

Вы можете использовать мощность объекта и стандартную сортировку ключей, которые можно использовать в качестве индексов массива (положительные 32-разрядные числа).

Эта попытка состоит из двух частей

  1. считать все числа

  2. итерирует все ключи объекта по их внешнему виду и

    1. проверьте, есть ли пропущенное число между фактическим элементом и предыдущим элементом. Если это так, присвойте пропущенные значения,

    2. проверьте счет и нажмите клавишу, если счет больше единицы.

Этот код завершается за 7410 мс. 

function findDupsMiss(arr) {
    var hash = Object.create(null),
        i = arr.length,
        l,
        v,
        keys,
        missing,
        dupes = [],
        previous, item;

    while (i--) {
        v = arr[i];
        if (!hash[v]) {
            hash[v] = 0;
        }
        hash[v]++;
    }
    keys = Object.keys(hash);
    l = keys.length;
    for (i = 0; i < l; i++) {
        item = +keys[i];
        if (previous + 1 !== item) {
            missing = previous + 1;
        }        
        if (hash[item] > 1) {
            dupes.push(item);
        }
        previous = item;
    }
    return [missing, dupes];
}
...