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

Проверка уникальности элементов массива на JavaScript

Функция \( \operatorname{testUnique}(A) \) проверяет массив \( A \) на уникальность его элементов. Если все элементы массива уникальны (не имею дублей), то функция вернёт \( \text{true} \), в противном случае — \( \text{false} \). Время работы в худшем случае \( O(n^2) \).
function testUnique(A)
{   
    var n = A.length;
    for (var i = 0; i < n-1; i++)
     { for (var j = i+1; j < n; j++)
        { if (A[ i ] === A[j]) return false; }
     }
    return true;
}
Если массив A упорядочен, то не сложно составить более эффективный алгоритм проверки уникальности элементов, время работы которого в худшем случае \( O(n) \).
function testUniqueSort(A)
{   
    var n = A.length;   
    for (var i = 1; i < n; i++)
      { if (A[i-1] === A[ i ]) return false; } 
    return true;
}

Удаление повторяющихся элементов в массиве на JavaScript

Функция \( Unique(A) \), которая возвращает массив, содержащий только уникальные элементы \( A \). Элементами массива \( A \) могут быть как числа, так и строки.
function Unique(A)
{
    var n = A.length, k = 0, B = [];
    for (var i = 0; i < n; i++) 
     { var j = 0;
       while (j < k && B[j] !== A[ i ]) j++;
       if (j == k) B[k++] = A[ i ];
     }
    return B;
}
Если массив упорядочен, то эффективней этот алгоритм (время \( O(n) \)):
function UniqueSort(A)   // A - упорядоченный массив.
{
    var n = A.length, B = [A[0]];
    for (var i = 1, j = 1; i < n; i++) 
     { if (A[ i ] !== B[j-1]) B[j++] = A[ i ]; }
    return B; 
}

Получение уникальных элементов массива на JavaScript

Функция возвращает только уникальные элементы упорядоченного массива, то есть на выходе будет массив только с теми элементами входного упорядоченного массива, которые не имеют дубли.
function getUniqueElems(A)   // A - упорядоченный массив.
{   
    var n = A.length, B = [];
    for (var i = 1, j = 0, t; i < n+1; i++)
     { if (A[i-1] === A[ i ]) t = A[i-1];
       if (A[i-1] !== t) B[j++] = A[i-1];
     }
                    // На выходе массив только с теми элементами входного 
    return B;       //  упорядоченного массива, которые не имеют дубли.
}

Получение элементов массива, имеющих дубли, на JavaScript

Функция для получения элементов упорядоченного массива, имеющих дубли, то есть на выходе будет массив только с теми элементами входного, упорядоченного массива, которые имеют дубли
function getDublsSortArr(A)   // A - упорядоченный массив.
{   
    var n = A.length, B = [];
    
    for (var i = 1, j = 0; i < n; i++)
     { if (A[i-1] === A[ i ]) B[j++] = A[i-1]; }
     
    return UniqueSort(B);    //  Функцию UniqueSort см. выше.
}
Массивы и объекты JavaScript JavaScript 40
Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!