Эффективно получить уникальный список по идентификатору объекта - PullRequest
Новая
       1

Эффективно получить уникальный список по идентификатору объекта

1 голос
/ 28 января 2020

У меня есть массив projects. Каждый project имеет массив employees. Каждый сотрудник имеет уникальный идентификатор id. Я хотел бы объединить все employees из всех projects в массиве, но удалить дубликаты.

Сначала я подумал о создании Map<number, Employee>, ключом которого будет идентификатор сотрудника. Таким образом, я могу проверить, есть ли на карте уже сотрудник id в качестве ключа, и добавить его на карту, только если он не: 

this.projects.forEach(project => {
  project.employees.forEach(employee=> {
    if (!this.employeeIdToEmployeeMap.has(employee.id)) {
      this.employeeIdToEmployeeMap.set(employee.id, employee);
    }
  })
});

После этого я смог получить значения карты и преобразовать их в массив: 

this.employees = Array.from(this.employeeIdToEmployeeMap.values());

Теперь у меня есть все employees из всех projects без дубликатов.

Есть ли лучший способ сделать это? Можно ли это сделать за O (n)?

Ответы [ 2 ]

0 голосов
/ 28 января 2020

Существует тривиальное решение O (nlogn):

  1. поместить всех сотрудников в список
  2. отсортировать список
  3. добавить сотрудников в новый список, а пропуск последовательных дубликатов

Какова сложность вашего решения? Что ж, преобразование карты в список должно быть O (n) при любой разумной реализации карты. Внешнее тело l oop выполняется n раз. Итак, вопрос в том, какова сложность, подразумеваемая добавлением элемента на карту? Время наихудшего случая является явно линейным (при условии, что основанный на списке блок и открытое хеширование; может быть log (n), если используется дерево или что-то другое), время в лучшем случае является постоянным. Здесь, поскольку наша проблема заключается в размещении n элементов на карте, нам нужно знать амортизируемую сложность. Используя резервное хранилище с изменяемым размером и мультипликативное расширение, когда оно обнаруживает, что в нем не хватает места, я ожидаю, что возможно получить амортизированную сложность O (1) для операции добавления. Если это то, как работает ваша карта, то у вас есть O (1) при условии хорошей функции ha sh.

0 голосов
/ 28 января 2020

Вы можете использовать метод Reduce для достижения этого: 

const projects: { employees: { id: any }[] }[] = [
    { employees: [{ id: 2 }, { id: 7 }] },
    { employees: [{ id: 5 }, { id: 7 }] }
];

const map = projects.reduce((employees, project) => ({
    ...employees,
    ...project.employees.reduce((emps, employee) => ({
        ...emps,
        ...(emps[employee.id] ? {} : { [employee.id]: employee })
    }), employees as any)
}), {} as any)

console.log(Object.values(map)); // Prints: [ {id: 2}, {id: 5}, {id: 7}
...