Javascript поиск одинаковых чисел массива
Задача.
Написать функцию, которая находит в массиве значения, повторяющиеся два и более раз, и возвращает их.
Решение.
Предложу два варианта решения. Первый вариант – классический, более длинный в плане кода, и возможно, немного более сложный для понимания, но и более оптимальный. Т.е. в данном алгоритме нет никаких лишних шагов и его можно использовать для больших массивов.
Второй вариант – более короткий в записи и более очевидный, но будет дольше выполняться в случае больших массивов, поскольку содержит предварительную сортировку массива.
Обращаю внимание, что оба варианта в результате выдают уникальные значения. Т.е., если исходный массив содержит, например, значение 5 более 2-х раз, то в результате 5 будет выведено один раз. Если по условию задачи этого не требуется, то в коде нужно убрать блоки проверки уникальности результата.
Вариант 1:
Суть алгоритма в том, что внешним циклом мы проходим исходный массив слева-направо, а внутренним циклом идем от текущего элемента в обратную сторону справа-налево. Более подробно данный метод рассматривался в статье Подсчет количества уникальных чисел в массиве.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
var arr = [1,5,7,1,8,4,3,5,5,9,0,0,0,0]; function duplicate_values(arr) { var arr_res = []; // результирующий массив /* проход по массиву слева-направо */ for (var i=1; i < arr.length; i++) { /* проходим массив в обратном порядке, начиная с элемента arr[i-1] */ for (var j=i-1; j >= 0; j--) { /* если ранее в массиве уже встречался элемент с таким же значением как и у текущего, то помещаем это значение в результирующий массив (предварительно проверив, нет ли там уже такого значения), завершаем внутренний цикл и переходим на следующую итерацию внешнего цикла*/ if (arr[j] == arr[i]) { var is_unique = true; // флаг уникальности элемента for (var k=0; k < arr_res.length; k++) { if (arr_res[k] == arr[i]) { is_unique = false; break; } } if (is_unique) { arr_res.push(arr[i]); } break; } } } return arr_res; } document.write(duplicate_values(arr)); |
Вариант 2:
Во втором варианте решения, мы сначала сортируем массив с помощью метода sort() и после этого нам не нужно делать обратный ход по массиву, как в предыдущем варианте решения. Нам достаточно сравнить значения текущего и предыдущего элемента. Данная методика применялась при решении задачи, описанной в статье Все ли элементы массива различны.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
var arr = [1,5,7,1,8,4,3,5,5,9,0,0,0,0]; function duplicate_values(arr) { arr_res = []; arr.sort(); for (var i=1; i < arr.length; i++) { if (arr[i] == arr[i-1]) { var is_unique = true; for (var k=0; k < arr_res.length; k++) { if (arr_res[k] == arr[i]) { is_unique = false; break; } } if (is_unique) { arr_res.push(arr[i]); } } } return arr_res; } document.write(duplicate_values(arr)); |
Цикл проверки наличия элемента в результирующем массиве можно заменить на следующую конструкцию:
|
1 2 3 4 5 6 7 8 |
var idx = arr_res.indexOf(arr[i]); if (idx >= 0) { is_unique = false; } |
Надеюсь, тема раскрыта. Если есть вопросы – спрашивайте, постараюсь ответить.
Свежие комментарии