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

Question

У меня есть массив, который содержит дубликаты

array = ["String 1", "string 2", "STRING 1", "String 2", "String 3", "String 1"]

Я хочу избавиться от дубликатов (без учета регистра) и создать новый массив, который подсчитывает дубликаты.

В одном из ответов я увидел эту функцию:

function count_array(arr) {
    var a = [], b = [], prev;

    arr.sort();
    for ( var i = 0; i < arr.length; i++ ) {
        if ( arr[i] !== prev ) {
             a.push(arr[i]);
             b.push(1);
        } else {
             b[b.length-1]++;
        }
        prev = arr[i];
     }
     return [a, b];
 }

, которая возвращает два массива:

First array: ["String 1", "String 2", "STRING 1", "String 3"]
Second array: [2, 2, 1, 1]

Это не без учета регистра, я хочу, чтобы все экземплярыиз String 1, STRING 1, string 1, StRING 1 следует рассматривать как String 1.

Также есть ли лучший способ сделать это для больших массивов?например длина массива 10К?

Answer 1

Это можно сделать кратко, используя Array.reduce для создания карты, ключами которой являются элементы вашего массива в нижнем регистре, а значения - их количество.Затем получите уникальные предметы с помощью Object.keys() и подсчитайте с помощью Object.values():

const array = ["String 1", "string 2", "STRING 1", "String 2", "String 3", "String 1"];

const map = array.reduce((acc, x) => {
  const xLower = x.toLocaleLowerCase();
  acc[xLower] = (acc[xLower] || 0) + 1;
  return acc;
}, {});

console.log(map);
console.log(Object.keys(map));
console.log(Object.values(map));

Answer 2

Если вы спрашиваете о самом быстром способе сделать это, это должно быть сделано в Big-O(N) асимптотически:

1. Во-первых, вам нужна хеш-карта для хранения всех ваших прошлых строк;
2. Во-вторых, вам нужно перебрать заданный массив, поместив его значения в хеш-карту;
3. Наконец, вам нужно увеличивать счетчик строки в хеш-карте каждый раз, когда она встречается.

Это может быть реализовано так:

const arr = [...];
const map = {};

for (let i = 0; i <= arr.length - 1; i++) {
    const str = arr[i].toLowerCase();

    if (str in map) {
        map[str]++;

        // keep in mind that removing element from an array costs O(N)
        arr[i] = undefined;
    } else {
        map[str] = 1;
    }
}

// now you have the hash map that represents all strings and its numbers of appearances in the given array
doSomething(map);

// finally return filtered result
return arr.filter(str => str !== undefined);

Answer 3

Уменьшите массив строк до объекта, используя строки в качестве ключей и количество появлений в качестве значений.Используйте Object.keys() для получения первого массива и Object.values() для второго:

const array = ["String 1", "string 2", "STRING 1", "String 2", "String 3", "String 1"]

const counts = array.reduce((r, s) => {
  const key = s[0].toUpperCase() + s.substring(1).toLowerCase();
  
  r[key] = (r[key] || 0) + 1;
  
  return r;
}, {});

const first = Object.keys(counts);
const second = Object.values(counts);

console.log(first);
console.log(second);

Чтобы отсортировать результат по количеству дубликатов, используйте Object.entries(), чтобы преобразовать результаты сокращения в массив пар.Сортировать по 2-му значению (количество).Чтобы получить два массива, используйте Array.map().

const array = ["String 1", "string 2", "STRING 1", "String 2", "String 3", "String 1"]

const counts = Object.entries(array.reduce((r, s) => {
  const key = s[0].toUpperCase() + s.substring(1).toLowerCase();
  
  r[key] = (r[key] || 0) + 1;
  
  return r;
}, {}))
.sort(([, a], [, b]) => b - a);

const first = counts.map(([s]) => s);
const second = counts.map(([, n]) => n);

console.log(first);
console.log(second);

Answer 4

Вы можете взять некоторые функции и отфильтровать норализованные значения с их подсчетом.

const
    normalize = s => s.toLowerCase(),
    getFirst = a => a,
    mapCount = (m, k) => m.set(k, (m.get(k) || 0) + 1),
    array = ["String 1", "string 2", "STRING 1", "String 2", "String 3", "String 1"],
    map = new Map,
    array1 = array.filter(v => (k => getFirst(!map.has(k), mapCount(map, k)))(normalize(v))),
    array2 = Array.from(map.values());

console.log(array1);
console.log(array2);

Если вы удовлетворены нормализованными строками в качестве набора результатов, вы можете воспользоваться этим подходом.

const
    normalize = s => s.toLowerCase(),
    mapCount = (m, k) => m.set(k, (m.get(k) || 0) + 1),
    array = ["String 1", "string 2", "STRING 1", "String 2", "String 3", "String 1"],
    map = array.reduce((m, v) => mapCount(m, normalize(v)), new Map),
    array1 = Array.from(map.keys()),
    array2 = Array.from(map.values());

console.log(array1);
console.log(array2);

Answer 5

.sort() - это процесс O(N log N) - если вам требуется для сортировки результатов, сделайте это в самом конце, если вас беспокоит скорость.Если вам не нужно сортировать результаты, используйте вместо этого Set (или Map) для проверки на наличие дубликатов, вместо проверки отсортированного массива для аналогичных элементов в соседних обозначениях.

array = ["String 1", "string 2", "STRING 1", "String 2", "String 3", "String 1"]
function count_array(arr) {
  const result = [];
  const map = new Map();
  arr.forEach((str) => {
    const lower = str.toLowerCase();
    const currCount = map.get(lower) || 0;
    if (!currCount) {
      result.push(str);
    }
    map.set(lower, currCount + 1);
  });
  console.log([...map.values()]);
  return result.sort();
}
console.log(count_array(array));

Вы можете использовать цикл for вместо forEach, если хотите, цикл for будет немного быстрее, хотя читать IMO будет немного сложнее:

array = ["String 1", "string 2", "STRING 1", "String 2", "String 3", "String 1"]
function count_array(arr) {
  const result = [];
  const map = new Map();
  for (let i = 0, { length } = arr; i < length; i++) {
    const str = arr[i];
    const lower = str.toLowerCase();
    const currCount = map.get(lower) || 0;
    if (!currCount) {
      result.push(str);
    }
    map.set(lower, currCount + 1);
  }
  console.log([...map.values()]);
  return result.sort();
}
console.log(count_array(array));