Массивы: методы

В этой главе мы рассмотрим встроенные методы массивов JavaScript.

Метод split

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

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

var names = 'Маша, Петя, Марина, Василий';

var arr = names.split(', ');

for (var i = 0; i < arr.length; i++) {
  alert( 'Вам сообщение ' + arr[i] );
}
Второй аргумент split

У метода split есть необязательный второй аргумент – ограничение на количество элементов в массиве. Если их больше, чем указано – остаток массива будет отброшен:

alert( "a,b,c,d".split(',', 2) ); // a,b
Разбивка по буквам

Вызов split с пустой строкой разобьёт по буквам:

var str = "тест";

alert( str.split('') ); // т,е,с,т

Метод join

Вызов arr.join(str) делает в точности противоположное split. Он берет массив и склеивает его в строку, используя str как разделитель.

Например:

var arr = ['Маша', 'Петя', 'Марина', 'Василий'];

var str = arr.join(';');

alert( str ); // Маша;Петя;Марина;Василий
new Array + join = Повторение строки

Код для повторения строки 3 раза:

alert( new Array(4).join("ля") ); // ляляля

Как видно, new Array(4) делает массив без элементов длины 4, который join объединяет в строку, вставляя между его элементами строку "ля".

В результате, так как элементы пусты, получается повторение строки. Такой вот небольшой трюк.

Удаление из массива

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

var arr = ["Я", "иду", "домой"];

delete arr[1]; // значение с индексом 1 удалено

// теперь arr = ["Я", undefined, "домой"];
alert( arr[1] ); // undefined

Да, элемент удален из массива, но не так, как нам этого хочется. Образовалась «дырка».

Это потому, что оператор delete удаляет пару «ключ-значение». Это – все, что он делает. Обычно же при удалении из массива мы хотим, чтобы оставшиеся элементы сдвинулись и заполнили образовавшийся промежуток.

Поэтому для удаления используются специальные методы: из начала – shift, с конца – pop, а из середины – splice, с которым мы сейчас познакомимся.

Метод splice

Метод splice – это универсальный раскладной нож для работы с массивами. Умеет все: удалять элементы, вставлять элементы, заменять элементы – по очереди и одновременно.

Его синтаксис:

arr.splice(index[, deleteCount, elem1, ..., elemN])
Удалить deleteCount элементов, начиная с номера index, а затем вставить elem1, ..., elemN на их место. Возвращает массив из удалённых элементов.

Этот метод проще всего понять, рассмотрев примеры.

Начнём с удаления:

var arr = ["Я", "изучаю", "JavaScript"];

arr.splice(1, 1); // начиная с позиции 1, удалить 1 элемент

alert( arr ); //  осталось ["Я", "JavaScript"]

В следующем примере мы удалим 3 элемента и вставим другие на их место:

var arr = ["Я", "сейчас", "изучаю", "JavaScript"];

// удалить 3 первых элемента и добавить другие вместо них
arr.splice(0, 3, "Мы", "изучаем")

alert( arr ) // теперь ["Мы", "изучаем", "JavaScript"]

Здесь видно, что splice возвращает массив из удаленных элементов:

var arr = ["Я", "сейчас", "изучаю", "JavaScript"];

// удалить 2 первых элемента
var removed = arr.splice(0, 2);

alert( removed ); // "Я", "сейчас" <-- array of removed elements

Метод splice также может вставлять элементы без удаления, для этого достаточно установить deleteCount в 0:

var arr = ["Я", "изучаю", "JavaScript"];

// с позиции 2
// удалить 0
// вставить "сложный", "язык"
arr.splice(2, 0, "сложный", "язык");

alert( arr ); // "Я", "изучаю", "сложный", "язык", "JavaScript"

Допускается использование отрицательного номера позиции, которая в этом случае отсчитывается с конца:

var arr = [1, 2, 5]

// начиная с позиции индексом -1 (перед последним элементом)
// удалить 0 элементов,
// затем вставить числа 3 и 4
arr.splice(-1, 0, 3, 4);

alert( arr ); // результат: 1,2,3,4,5

Метод slice

Метод slice(begin, end) копирует участок массива от begin до end, не включая end. Исходный массив при этом не меняется.

Например:

var arr = ["Почему", "надо", "учить", "JavaScript"];

var arr2 = arr.slice(1, 3); // элементы 1, 2 (не включая 3)

alert( arr2 ); // надо, учить

Аргументы ведут себя так же, как и в строковом slice:

  • Если не указать end – копирование будет до конца массива:

    var arr = ["Почему", "надо", "учить", "JavaScript"];
    
    alert( arr.slice(1) ); // взять все элементы, начиная с номера 1
  • Можно использовать отрицательные индексы, они отсчитываются с конца:

    var arr2 = arr.slice(-2); // копировать от 2-го элемента с конца и дальше
  • Если вообще не указать аргументов – скопируется весь массив:

    var fullCopy = arr.slice();
Совсем как в строках

Синтаксис метода slice одинаков для строк и для массивов. Тем проще его запомнить.

Сортировка, метод sort(fn)

Метод sort() сортирует массив на месте. Например:

var arr = [ 1, 2, 15 ];

arr.sort();

alert( arr );  // 1, 15, 2

Не заметили ничего странного в этом примере?

Порядок стал 1, 15, 2, это точно не сортировка чисел. Почему?

Это произошло потому, что по умолчанию sort сортирует, преобразуя элементы к строке.

Поэтому и порядок у них строковый, ведь "2" > "15".

Свой порядок сортировки

Для указания своего порядка сортировки в метод arr.sort(fn) нужно передать функцию fn от двух элементов, которая умеет сравнивать их.

Внутренний алгоритм функции сортировки умеет сортировать любые массивы – апельсинов, яблок, пользователей, и тех и других и третьих – чего угодно. Но для этого ему нужно знать, как их сравнивать. Эту роль и выполняет fn.

Если эту функцию не указать, то элементы сортируются как строки.

Например, укажем эту функцию явно, отсортируем элементы массива как числа:

function compareNumeric(a, b) {
  if (a > b) return 1;
  if (a < b) return -1;
}

var arr = [ 1, 2, 15 ];

arr.sort(compareNumeric);

alert(arr);  // 1, 2, 15

Обратите внимание, мы передаём в sort() именно саму функцию compareNumeric, без вызова через скобки. Был бы ошибкой следующий код:

arr.sort( compareNumeric() );  // не сработает

Как видно из примера выше, функция, передаваемая sort, должна иметь два аргумента.

Алгоритм сортировки, встроенный в JavaScript, будет передавать ей для сравнения элементы массива. Она должна возвращать:

  • Положительное значение, если a > b,
  • Отрицательное значение, если a < b,
  • Если равны – можно 0, но вообще – не важно, что возвращать, если их взаимный порядок не имеет значения.
Алгоритм сортировки

В методе sort, внутри самого интерпретатора JavaScript, реализован универсальный алгоритм сортировки. Как правило, это ««быстрая сортировка»», дополнительно оптимизированная для небольших массивов.

Он решает, какие пары элементов и когда сравнивать, чтобы отсортировать побыстрее. Мы даём ему функцию – способ сравнения, дальше он вызывает её сам.

Кстати, те значения, с которыми sort вызывает функцию сравнения, можно увидеть, если вставить в неё alert:

[1, -2, 15, 2, 0, 8].sort(function(a, b) {
  alert( a + " <> " + b );
});
Сравнение compareNumeric в одну строку

Функцию compareNumeric для сравнения элементов-чисел можно упростить до одной строчки.

function compareNumeric(a, b) {
  return a - b;
}

Эта функция вполне подходит для sort, так как возвращает положительное число, если a > b, отрицательное, если наоборот, и 0, если числа равны.

reverse

Метод arr.reverse() меняет порядок элементов в массиве на обратный.

var arr = [1, 2, 3];
arr.reverse();

alert( arr ); // 3,2,1

concat

Метод arr.concat(value1, value2, … valueN) создаёт новый массив, в который копируются элементы из arr, а также value1, value2, ... valueN.

Например:

var arr = [1, 2];
var newArr = arr.concat(3, 4);

alert( newArr ); // 1,2,3,4

У concat есть одна забавная особенность.

Если аргумент concat – массив, то concat добавляет элементы из него.

Например:

var arr = [1, 2];

var newArr = arr.concat([3, 4], 5); // то же самое, что arr.concat(3,4,5)

alert( newArr ); // 1,2,3,4,5

indexOf/lastIndexOf

Эти методы не поддерживаются в IE8-. Для их поддержки подключите библиотеку ES5-shim.

Метод «arr.indexOf(searchElement[, fromIndex])» возвращает номер элемента searchElement в массиве arr или -1, если его нет.

Поиск начинается с номера fromIndex, если он указан. Если нет – с начала массива.

Для поиска используется строгое сравнение ===.

Например:

var arr = [1, 0, false];

alert( arr.indexOf(0) ); // 1
alert( arr.indexOf(false) ); // 2
alert( arr.indexOf(null) ); // -1

Как вы могли заметить, по синтаксису он полностью аналогичен методу indexOf для строк.

Метод «arr.lastIndexOf(searchElement[, fromIndex])» ищет справа-налево: с конца массива или с номера fromIndex, если он указан.

Методы indexOf/lastIndexOf осуществляют поиск перебором

Если нужно проверить, существует ли значение в массиве – его нужно перебрать. Только так. Внутренняя реализация indexOf/lastIndexOf осуществляет полный перебор, аналогичный циклу for по массиву. Чем длиннее массив, тем дольше он будет работать.

Коллекция уникальных элементов

Рассмотрим задачу – есть коллекция строк, и нужно быстро проверять: есть ли в ней какой-то элемент. Массив для этого не подходит из-за медленного indexOf. Но подходит объект! Доступ к свойству объекта осуществляется очень быстро, так что можно сделать все элементы ключами объекта и проверять, есть ли уже такой ключ.

Например, организуем такую проверку для коллекции строк "div", "a" и "form":

var store = {}; // объект для коллекции

var items = ["div", "a", "form"];

for (var i = 0; i < items.length; i++) {
  var key = items[i]; // для каждого элемента создаём свойство
  store[key] = true; // значение здесь не важно
}

Теперь для проверки, есть ли ключ key, достаточно выполнить if (store[key]). Если есть – можно использовать значение, если нет – добавить.

Такое решение работает только со строками, но применимо к любым элементам, для которых можно вычислить строковый «уникальный ключ».

Object.keys(obj)

Ранее мы говорили о том, что свойства объекта можно перебрать в цикле for..in.

Если мы хотим работать с ними в виде массива, то к нашим услугам – замечательный метод Object.keys(obj). Он поддерживается везде, кроме IE8-:

var user = {
  name: "Петя",
  age: 30
}

var keys = Object.keys(user);

alert( keys ); // name, age

Итого

Методы массивов:

  • push/pop, shift/unshift, splice – для добавления и удаления элементов.
  • join/split – для преобразования строки в массив и обратно.
  • slice – копирует участок массива.
  • sort – для сортировки массива. Если не передать функцию сравнения – сортирует элементы как строки.
  • reverse – меняет порядок элементов на обратный.
  • concat – объединяет массивы.
  • indexOf/lastIndexOf – возвращают позицию элемента в массиве (не поддерживается в IE8-).

Дополнительно:

  • Object.keys(arr) возвращает массив свойств объекта.

Изученных нами методов достаточно в 95% случаях, но существуют и другие. Для знакомства с ними рекомендуется заглянуть в справочник Array и Array в Mozilla Developer Network.

Задачи

важность: 5

В объекте есть свойство className, которое содержит список «классов» – слов, разделенных пробелом:

var obj = {
  className: 'open menu'
}

Создайте функцию addClass(obj, cls), которая добавляет в список класс cls, но только если его там еще нет:

addClass(obj, 'new'); // obj.className='open menu new'
addClass(obj, 'open'); // без изменений (класс уже существует)
addClass(obj, 'me'); // obj.className='open menu new me'

alert( obj.className ); // "open menu new me"

P.S. Ваша функция не должна добавлять лишних пробелов.

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

Решение заключается в превращении obj.className в массив при помощи split. После этого в нем можно проверить наличие класса, и если нет – добавить.

function addClass(obj, cls) {
  var classes = obj.className ? obj.className.split(' ') : [];

  for (var i = 0; i < classes.length; i++) {
    if (classes[i] == cls) return; // класс уже есть
  }

  classes.push(cls); // добавить

  obj.className = classes.join(' '); // и обновить свойство
}

var obj = {
  className: 'open menu'
};

addClass(obj, 'new');
addClass(obj, 'open');
addClass(obj, 'me');
alert(obj.className) // open menu new me

P.S. «Альтернативный» подход к проверке наличия класса вызовом obj.className.indexOf(cls) был бы неверным. В частности, он найдёт cls = "menu" в строке классов obj.className = "open mymenu".

P.P.S. Проверьте, нет ли в вашем решении присвоения obj.className += " " + cls. Не добавляет ли оно лишний пробел в случае, если изначально obj.className = ""?

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

важность: 3

Напишите функцию camelize(str), которая преобразует строки вида «my-short-string» в «myShortString».

То есть, дефисы удаляются, а все слова после них получают заглавную букву.

Например:

camelize("background-color") == 'backgroundColor';
camelize("list-style-image") == 'listStyleImage';
camelize("-webkit-transition") == 'WebkitTransition';

Такая функция полезна при работе с CSS.

P.S. Вам пригодятся методы строк charAt, split и toUpperCase.

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

Идея

Задача может быть решена несколькими способами. Один из них – разбить строку по дефису str.split('-'), затем последовательно сконструировать новую.

Решение

Разобьем строку в массив, а затем преобразуем его элементы и сольём обратно:

function camelize(str) {
  var arr = str.split('-');

  for (var i = 1; i < arr.length; i++) {
    // преобразовать: первый символ с большой буквы
    arr[i] = arr[i].charAt(0).toUpperCase() + arr[i].slice(1);
  }

  return arr.join('');
}

alert( camelize("background-color") ); // backgroundColor
alert( camelize("list-style-image") ); // listStyleImage
alert( camelize("-webkit-transition") ); // WebkitTransition

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

важность: 5

У объекта есть свойство className, которое хранит список «классов» – слов, разделенных пробелами:

var obj = {
  className: 'open menu'
};

Напишите функцию removeClass(obj, cls), которая удаляет класс cls, если он есть:

removeClass(obj, 'open'); // obj.className='menu'
removeClass(obj, 'blabla'); // без изменений (нет такого класса)

P.S. Дополнительное усложнение. Функция должна корректно обрабатывать дублирование класса в строке:

obj = {
  className: 'my menu menu'
};
removeClass(obj, 'menu');
alert( obj.className ); // 'my'

Лишних пробелов после функции образовываться не должно.

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

Решение заключается в том, чтобы разбить className в массив классов, а затем пройтись по нему циклом. Если класс есть – удаляем его splice, заново объединяем массив в строку и присваиваем объекту.

function removeClass(obj, cls) {
  var classes = obj.className.split(' ');

  for (var i = 0; i < classes.length; i++) {
    if (classes[i] == cls) {
      classes.splice(i, 1); // удалить класс
      i--; // (*)
    }
  }
  obj.className = classes.join(' ');

}

var obj = {
  className: 'open menu menu'
}

removeClass(obj, 'blabla');
removeClass(obj, 'menu')
alert(obj.className) // open

В примере выше есть тонкий момент. Элементы массива проверяются один за другим. При вызове splice удаляется текущий, i-й элемент, и те элементы, которые идут дальше, сдвигаются на его место.

Таким образом, на месте i оказывается новый, непроверенный элемент.

Чтобы это учесть, строчка (*) уменьшает i, чтобы следующая итерация цикла заново проверила элемент с номером i. Без нее функция будет работать с ошибками.

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

важность: 4

Создайте функцию filterRangeInPlace(arr, a, b), которая получает массив с числами arr и удаляет из него все числа вне диапазона a..b. То есть, проверка имеет вид a ≤ arr[i] ≤ b. Функция должна менять сам массив и ничего не возвращать.

Например:

arr = [5, 3, 8, 1];

filterRangeInPlace(arr, 1, 4); // удалены числа вне диапазона 1..4

alert( arr ); // массив изменился: остались [3, 1]

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

function filterRangeInPlace(arr, a, b) {

  for (var i = 0; i < arr.length; i++) {
    var val = arr[i];
    if (val < a || val > b) {
      arr.splice(i--, 1);
    }
  }

}

var arr = [5, 3, 8, 1];

filterRangeInPlace(arr, 1, 4);
alert( arr ); // [3, 1]

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

важность: 5

Как отсортировать массив чисел в обратном порядке?

var arr = [5, 2, 1, -10, 8];

// отсортируйте?

alert( arr ); // 8, 5, 2, 1, -10
var arr = [5, 2, 1, -10, 8];

function compareReversed(a, b) {
  return b - a;
}

arr.sort(compareReversed);

alert( arr );
важность: 5

Есть массив строк arr. Создайте массив arrSorted – из тех же элементов, но отсортированный.

Исходный массив не должен меняться.

var arr = ["HTML", "JavaScript", "CSS"];

// ... ваш код ...

alert( arrSorted ); // CSS, HTML, JavaScript
alert( arr ); // HTML, JavaScript, CSS (без изменений)

Постарайтесь сделать код как можно короче.

Для копирования массива используем slice(), и тут же – сортировку:

var arr = ["HTML", "JavaScript", "CSS"];

var arrSorted = arr.slice().sort();

alert( arrSorted );
alert( arr );
важность: 3

Используйте функцию sort для того, чтобы «перетрясти» элементы массива в случайном порядке.

var arr = [1, 2, 3, 4, 5];

arr.sort(ваша функция);

alert( arr ); // элементы в случайном порядке, например [3,5,1,2,4]

Подсказка

Функция сортировки должна возвращать случайный результат сравнения. Используйте для этого Math.random.

Решение

Обычно Math.random() возвращает результат от 0 до 1. Вычтем 0.5, чтобы область значений стала [-0.5 ... 0.5).

var arr = [1, 2, 3, 4, 5];

function compareRandom(a, b) {
  return Math.random() - 0.5;
}

arr.sort(compareRandom);

alert( arr ); // элементы в случайном порядке, например [3,5,1,2,4]
важность: 5

Напишите код, который отсортирует массив объектов people по полю age.

Например:

var vasya = { name: "Вася", age: 23 };
var masha = { name: "Маша", age: 18 };
var vovochka = { name: "Вовочка", age: 6 };

var people = [ vasya , masha , vovochka ];

... ваш код ...

// теперь people: [vovochka, masha, vasya]
alert(people[0].age) // 6

Выведите список имён в массиве после сортировки.

Для сортировки объявим и передадим в sort функцию, которая сравнивает объекты по полю age:

// Наша функция сравнения
function compareAge(personA, personB) {
  return personA.age - personB.age;
}

// проверка
var vasya = { name: "Вася", age: 23 };
var masha = { name: "Маша", age: 18 };
var vovochka = { name: "Вовочка", age: 6 };

var people = [ vasya , masha , vovochka ];

people.sort(compareAge);

// вывести
for(var i = 0; i < people.length; i++) {
  alert(people[i].name); // Вовочка Маша Вася
}
важность: 5

Односвязный список – это структура данных, которая состоит из элементов, каждый из которых хранит ссылку на следующий. Последний элемент может не иметь ссылки, либо она равна null.

Например, объект ниже задаёт односвязный список, в next хранится ссылка на следующий элемент:

var list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

Графическое представление этого списка:

Альтернативный способ создания:

var list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

Такая структура данных интересна тем, что можно очень быстро разбить список на части, объединить списки, удалить или добавить элемент в любое место, включая начало. При использовании массива такие действия требуют обширных перенумерований.

Задачи:

  1. Напишите функцию printList(list), которая выводит элементы списка по очереди, при помощи цикла.
  2. Напишите функцию printList(list) при помощи рекурсии.
  3. Напишите функцию printReverseList(list), которая выводит элементы списка в обратном порядке, при помощи рекурсии. Для списка выше она должна выводить 4,3,2,1
  4. Сделайте вариант printReverseList(list), использующий не рекурсию, а цикл.

Как лучше – с рекурсией или без?

Вывод списка в цикле

var list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printList(list) {
  var tmp = list;

  while (tmp) {
    alert( tmp.value );
    tmp = tmp.next;
  }

}

printList(list);

Обратите внимание, что для прохода по списку используется временная переменная tmp, а не list. Можно было бы и бегать по списку, используя входной параметр функции:

function printList(list) {

  while(list) {
    alert( list.value );
    list = list.next;
  }

}

…Но при этом мы в будущем не сможем расширить функцию и сделать со списком что-то ещё, ведь после окончания цикла начало списка уже нигде не хранится.

Поэтому и используется временная переменная – чтобы сделать код расширяемым, и, кстати, более понятным, ведь роль tmp – исключительно обход списка, как i в цикле for.

Вывод списка с рекурсией

Рекурсивный вариант printList(list) следует простой логике: вывести текущее значение (1), а затем пропустить через себя следующее (2):

var list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printList(list) {

  alert( list.value ); // (1)

  if (list.next) {
    printList(list.next); // (2)
  }

}

printList(list);

Обратный вывод с рекурсией

Обратный вывод – почти то же самое, что прямой, просто сначала мы обрабатываем следующее значение, а потом – текущее:

var list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printReverseList(list) {

  if (list.next) {
    printReverseList(list.next);
  }

  alert( list.value );
}

printReverseList(list);

Обратный вывод без рекурсии

var list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printReverseList(list) {
  var arr = [];
  var tmp = list;

  while (tmp) {
    arr.push(tmp.value);
    tmp = tmp.next;
  }

  for (var i = arr.length - 1; i >= 0; i--) {
    alert( arr[i] );
  }
}

printReverseList(list);

Обратный вывод без рекурсии быстрее.

По сути, рекурсивный вариант и нерекурсивный работают одинаково: они проходят список и запоминают его элементы, а потом выводят в обратном порядке.

В случае с массивом это очевидно, а для рекурсии запоминание происходит в стеке (внутренней специальной структуре данных): когда вызывается вложенная функция, то интерпретатор сохраняет в стек текущие параметры. Вложенные вызовы заполняют стек, а потом он выводится в обратном порядке.

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

Преимущество рекурсии, с другой стороны – более короткий и, зачастую, более простой код.

важность: 3

Анаграммы – слова, состоящие из одинакового количества одинаковых букв, но в разном порядке. Например:

воз - зов
киборг - гробик
корсет - костер - сектор

Напишите функцию aclean(arr), которая возвращает массив слов, очищенный от анаграмм.

Например:

var arr = ["воз", "киборг", "корсет", "ЗОВ", "гробик", "костер", "сектор"];

alert( aclean(arr) ); // "воз,киборг,корсет" или "ЗОВ,гробик,сектор"

Из каждой группы анаграмм должно остаться только одно слово, не важно какое.

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

Решение

Чтобы обнаружить анаграммы, разобьём каждое слово на буквы и отсортируем их. В отсортированном по буквам виде все анаграммы одинаковы.

Например:

воз, зов -> взо
киборг, гробик -> бгикор
...

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

Для этого воспользуемся вспомогательным объектом, в который будем записывать слова по отсортированному ключу:

function aclean(arr) {
  // этот объект будем использовать для уникальности
  var obj = {};

  for (var i = 0; i < arr.length; i++) {
    // разбить строку на буквы, отсортировать и слить обратно
    var sorted = arr[i].toLowerCase().split('').sort().join(''); // (*)

    obj[sorted] = arr[i]; // сохраняет только одно значение с таким ключом
  }

  var result = [];

  // теперь в obj находится для каждого ключа ровно одно значение
  for (var key in obj) result.push(obj[key]);

  return result;
}

var arr = ["воз", "киборг", "корсет", "ЗОВ", "гробик", "костер", "сектор"];

alert( aclean(arr) );

Приведение слова к сортированному по буквам виду осуществляется цепочкой вызовов в строке (*).

Для удобства комментирования разобьём её на несколько строк (JavaScript это позволяет):

var sorted = arr[i] // ЗОВ
  .toLowerCase() // зов
  .split('') // ['з','о','в']
  .sort() // ['в','з','о']
  .join(''); // взо

Получится, что два разных слова 'ЗОВ' и 'воз' получат одинаковую отсортированную форму 'взо'.

Следующая строка:

obj[sorted] = arr[i];

В объект obj будет записано сначала первое из слов obj['взо'] = "воз", а затем obj['взо'] = 'ЗОВ'.

Обратите внимание, ключ – отсортирован, а само слово – в исходной форме, чтобы можно было потом получить его из объекта.

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

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

важность: 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 = {} и записывает в него все строки как имена свойств. А затем собирает свойства из объекта в массив через for..in. Дубликатов уже не будет.

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-()

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

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

Карта учебника

Комментарии

перед тем как писать…
  • Приветствуются комментарии, содержащие дополнения и вопросы по статье, и ответы на них.
  • Для одной строки кода используйте тег <code>, для нескольких строк кода — тег <pre>, если больше 10 строк — ссылку на песочницу (plnkr, JSBin, codepen…)
  • Если что-то непонятно в статье — пишите, что именно и с какого места.