Блог

Я пытаюсь удалить все повторяющиеся объекты между четырьмя массивами по предпочтению. Все массивы имеют уникальные элементы и не могут быть упорядочены. Вот картинка, которая пытается объяснить проблему:

Как вы можете видеть, если массив имеет более низкое предпочтение, элементы останутся внутри него. Например, объект с идентификатором «6» повторяется в массивах с предпочтением 2, 3 и 4. Таким образом, алгоритм должен обнаружить это и удалить эти объекты из массивов с предпочтением 3 и 4, потому что 2 < 3 < 4.

Итак, если входные данные:

   arr_p1 = [{ id: "892d" }, {id: "kla8x" }, {id: "sys32" }]
  arr_p2 = [{id: "saa1" }, { id: "892d" }]
  arr_p3 = [{ id: "kla8x" }, {id: "saa1" }, {id: "pp182" }]
  

вывод должен быть:

   arr_p1 = [{ id: "892d" }, {id: "kla8x" }, {id: "sys32" }]
  arr_p2 = [{id: "saa1" }]
  arr_p3 = [{id: "pp182" }]
  

Есть идеи о том, как решить эту ситуацию в хорошем порядке сложности?

Все массивы имеют ограниченный размер в 40 объектов.

Единственное, что я могу придумать, это отсортировать все объекты в каждом массиве по идентификатору. Затем возьмите наименьший идентификатор объекта, перемещающегося с указателем каждого списка, от самого низкого предпочтения (1) до самого высокого (4), и если он находится в одном из списков с более высокими предпочтениями, удалите его… но мне нужно сделать это, не изменяя порядок элементов…

Pd: Я использую JS и ES6.

Объедините все элементы в один массив, а затем сведите их к карте в обратном порядке с помощью Array.reduceRight() . Обратный порядок приведет к тому, что первые элементы будут переопределять последние элементы.

Теперь вы можете фильтровать каждый массив, используя карту и сохраняя только элементы, которые существуют на карте.

Сложность равна O (N1 N2 N3), где Nx — длина этого массива.

 const arr_p1 = [{ id: "892d" }, {id: "kla8x" }, {id: "sys32" }]
const arr_p2 = [{id: "saa1" }, { id: "892d" }]
const arr_p3 = [{ id: "kla8x" }, {id: "saa1" }, {id: "pp182" }]

// create an array of all items and reduce it in a reversed order to a Map
const dupsMap = [...arr_p1, ...arr_p2, ...arr_p3]
  // create the Map by using the `id` as the key, and the object as the value
  .reduceRight((acc, o) => acc.set(o.id, o), new Map())
  
const filterArr = arr => arr.filter(o =>
  dupsMap.get(o.id) === o // keep the item if it was the object that was used as value
)
  
const arr_p1f = filterArr(arr_p1)
const arr_p2f = filterArr(arr_p2)
const arr_p3f = filterArr(arr_p3)

console.log({ arr_p1f, arr_p2f, arr_p3f })  

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

 const dedupArrays = (...arrs) => {
  const dupsMap = arrs.flat() // convert arrays to a single array
    // a reduce right to create a Map of [id, object]
    .reduceRight((acc, o) => acc.set(o.id, o), new Map())
    
  // map the array of arrays, and filter each sub array
  return arrs.map(arr => arr.filter(o => dupsMap.get(o.id) === o))
}

const arr_p1 = [{ id: "892d" }, {id: "kla8x" }, {id: "sys32" }]
const arr_p2 = [{id: "saa1" }, { id: "892d" }]
const arr_p3 = [{ id: "kla8x" }, {id: "saa1" }, {id: "pp182" }]

const [arr_p1f, arr_p2f, arr_p3f] = dedupArrays(arr_p1, arr_p2, arr_p3)

console.log({ arr_p1f, arr_p2f, arr_p3f })  

Вы можете сгенерировать объект предпочтения (хэш-карту), чтобы сопоставить идентификатор с предпочтением. Запустите его из 3-го массива в первый, чтобы более низкий порядок переопределял более высокий.

Затем, когда у вас есть карта предпочтений, вы можете отфильтровать все массивы, проверив, соответствует ли предпочтение идентификатора текущему массиву.

 let arr_p1 = [{ id: "892d" }, {id: "kla8x" }, {id: "sys32" }];
let arr_p2 = [{id: "saa1" }, { id: "892d" }];
let arr_p3 = [{ id: "kla8x" }, {id: "saa1" }, {id: "pp182" }];

let pref = {};

arr_p3.forEach(e => pref[e.id] = 3);
arr_p2.forEach(e => pref[e.id] = 2);
arr_p1.forEach(e => pref[e.id] = 1);

arr_p1 = arr_p1.filter(e => pref[e.id] === 1);
arr_p2 = arr_p2.filter(e => pref[e.id] === 2);
arr_p3 = arr_p3.filter(e => pref[e.id] === 3);

console.log(arr_p1);
console.log(arr_p2);
console.log(arr_p3);  

У меня есть для вас несколько советов, а не полный ответ, поскольку я предполагаю, что это вопрос домашнего задания?

СТРАТЕГИИ

Создайте набор «уже просмотренных элементов»

Сверяйте каждый новый массив с этим, удаляя все повторяющиеся записи (в новом массиве).

Начните с наиболее предпочтительного массива

Таким образом, всякий раз, когда что-то удаляется, оно удаляется из менее предпочтительного массива.

Например, в псевдокоде

 let elementsSeen = new Set(   most preferred array of elements   )

for array in listOfArraysInDecreasingOrderOfPreference {

  for element in array {
    if element is in elementsSeen, delete it from array
  }
  elementsSeen = union of elementsSeen and array
}
  

Сложность

Каждый элемент должен быть просмотрен. Его нужно сравнивать с любым другим элементом, но сложность этого не должна быть огромной, потому что процесс `Set` может использовать хэши, т. Е. Не Нужно выполнять индивидуальное сравнение каждого входящего объекта с каждым существующим объектом. Почти все входящие объекты будут иметь значение хэш-таблицы, отличное от значений существующих объектов, что происходит быстро, за счет некоторого времени, потраченного на хеширование, и некоторой памяти, потраченной на таблицу.

В худшем случае, когда хеширование вам больше не помогает, это O (N x M), где N — количество массивов, а M — размер каждого.

Ваш вопрос подразумевает, что вы хотите изменить исходные массивы.

Так что, если вы все еще хотите изменить массивы, вы могли бы.

1. создайте НАБОР идентификаторов для каждого уровня.
2. Цикл каждого уровня назад, если какой-либо идентификатор находится на более высоком уровне, затем удалите из массива.

Здесь тоже есть пара оптимизаций, например. slice(0, -1), поэтому нам не нужно создавать НАБОР для последнего уровня, как мы проверяли предыдущие. Внутри цикла, как только известно, что элемент удален, используйте перерыв, чтобы перейти к следующему. Честно говоря, я понятия не имею, в чем сложность этого .. 🙂

например.

 const arr_p1 = 
  [{ id: "892d" }, {id: "kla8x" }, {id: "sys32" }];
const arr_p2 = 
  [{id: "saa1" }, { id: "892d" }];
const arr_p3 = 
  [{ id: "kla8x" }, {id: "saa1" }, {id: "pp182" }];
  
  
function dedupe(alist) {
  const hasList = alist.map(
    m => new Set(m.slice(0, -1).map(i => i.id)));
  for (let l = alist.length -1; l > 0; l --) {
    for (let i = alist[l].length -1; i >= 0; i --) {
      for (let h = 0; h < l; h  = 1) {
        if (hasList[h].has(alist[l][i].id)) {
          alist[l].splice(i, 1);
          break;
        }
      }
    }
  }
}


dedupe([arr_p1, arr_p2, arr_p3]);
console.log(arr_p1);
console.log(arr_p2);
console.log(arr_p3);