Вернуться к уроку

Оставить уникальные элементы массива

важность: 3

Пусть arr – массив строк.

Напишите функцию unique(arr), которая возвращает массив, содержащий только уникальные элементы arr.

Например:

function unique(arr) {
  /* ваш код */
}

var strings = ["кришна", "кришна", "харе", "харе",
  "харе", "харе", "кришна", "кришна", "8-()"
];

alert( unique(strings) ); // кришна, харе, 8-()

Открыть песочницу с тестами для задачи.

Решение перебором (медленное)

Пройдём по массиву вложенным циклом.

Для каждого элемента мы будем искать, был ли такой уже. Если был – игнорировать:

function unique(arr) {
  var result = [];

  nextInput:
    for (var i = 0; i < arr.length; i++) {
      var str = arr[i]; // для каждого элемента
      for (var j = 0; j < result.length; j++) { // ищем, был ли он уже?
        if (result[j] == str) continue nextInput; // если да, то следующий
      }
      result.push(str);
    }

  return result;
}

var strings = ["кришна", "кришна", "харе", "харе",
  "харе", "харе", "кришна", "кришна", "8-()"
];

alert( unique(strings) ); // кришна, харе, 8-()

Давайте посмотрим, насколько быстро он будет работать.

Предположим, в массиве 100 элементов. Если все они одинаковые, то result будет состоять из одного элемента и вложенный цикл будет выполняться сразу. В этом случае всё хорошо.

А если все, или почти все элементы разные?

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

  1. Для первого элемента – это обойдётся в 0 операций доступа к элементам result (он пока пустой).
  2. Для второго элемента – это обойдётся в 1 операцию доступа к элементам result.
  3. Для третьего элемента – это обойдётся в 2 операции доступа к элементам result.
  4. …Для n-го элемента – это обойдётся в n-1 операций доступа к элементам result.

Всего 0 + 1 + 2 + … + n-1 = (n-1)*n/2 = n2/2 – n/2 (как сумма арифметической прогрессии), то есть количество операций растёт примерно как квадрат от n.

Это очень быстрый рост. Для 100 элементов – 4950 операций, для 1000499500 (по формуле выше).

Поэтому такое решение подойдёт только для небольших массивов. Вместо вложенного for можно использовать и arr.indexOf, ситуация от этого не поменяется, так как indexOf тоже ищет перебором.

Решение с объектом (быстрое)

Наилучшая техника для выбора уникальных строк – использование вспомогательного объекта obj. Ведь название свойства в объекте, с одной стороны – строка, а с другой – всегда уникально. Повторная запись в свойство с тем же именем перезапишет его.

Например, если "харе" попало в объект один раз (obj["харе"] = true), то второе такое же присваивание ничего не изменит.

Решение ниже создаёт объект obj = {} и записывает в него все строки как имена свойств. А затем собирает свойства из объекта в массив через Object.keys(). Дубликатов уже не будет.

function unique(arr) {
  var obj = {};

  for (var i = 0; i < arr.length; i++) {
    var str = arr[i];
    obj[str] = true; // запомнить строку в виде свойства объекта
  }

  return Object.keys(obj); // или собрать ключи перебором для IE8-
}

var strings = ["кришна", "кришна", "харе", "харе",
  "харе", "харе", "кришна", "кришна", "8-()"
];

alert( unique(strings) ); // кришна, харе, 8-()

Так что можно положить все значения как ключи в объект, а потом достать.

Открыть решение с тестами в песочнице.