Самый эффективный алгоритм сортировки и удаления дубликатов для списка? - PullRequest
0 голосов
/ 31 августа 2018

Предположим, у меня есть такой список:

[ 2, 7, 2, 3, 1, 1, 4, 5, 3, 6, 4 ]

И я хочу отсортировать и удалить дубликаты, чтобы получить:

[ 1, 2, 3, 4, 5, 6, 7 ]

Я могу добиться этого, удалив дубликаты , а затем отсортировав:

const uniqueAndSorted = xs => [ ...new Set(xs) ].sort();

Однако это кажется неэффективным, так как я мог бы обнаружить дубликаты во время сортировки.

Каков оптимальный способ сортировки и удаления дубликатов из списка?

(реализации JavaScript предпочтительнее; функция должна быть неразрушающей)

Ответы [ 5 ]

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

Это зависит от количества дубликатов, которые у вас есть. Несколько копий затем сортируют, а затем удаляют быстрее. С другой стороны, если у вас много дубликатов, сначала создайте хэш-набор, а затем сортируйте - лучший вариант.

Источники: Какой самый эффективный способ удаления дубликатов и сортировки вектора?

https://www.geeksforgeeks.org/how-to-sort-a-big-array-with-many-repetitions/

Другой вариант - использовать «быструю сортировку по жирной оси» или «быструю сортировку по тройному разбиению», которая быстрее, чем быстрая сортировка, когда на входе много дубликатов:

https://www.toptal.com/developers/sorting-algorithms/quick-sort-3-way

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

Этого можно добиться с помощью набора ES6.

Например:

const uniqueAndSorted = xs => Array.from(new Set(xs)).sort();

uniqueAndSorted([ 2, 7, 2, 3, 1, 1, 4, 5, 3, 6, 4 ]) должен вернуться [1, 2, 3, 4, 5, 6, 7]

0 голосов
/ 31 августа 2018

Это работает, но лучше всего сравнить несколько методов:

function uniq_sort(a) {
    var seen = {};
    return a.filter(function(item) {
        return seen.hasOwnProperty(item) ? false : (seen[item] = true);
    }).sort();
}
0 голосов
/ 31 августа 2018
var myData = [ 2, 7, 2, 3, 1, 1, 4, 5, 3, 6, 4 ];

myData.reduce((x, y) => x.includes(y) ? x : [...x, y], []).sort() 
0 голосов
/ 31 августа 2018

Я не уверен, что это работает со всеми браузерами, но вы можете сделать следующее:

По крайней мере, в Chrome это работает:

function getSortedSetArray(arr) {
  var map = {};

  arr.forEach(function (elem) {
    map[elem] = true;
  })

  return Object.keys(map);
} 
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...