从数组中获取最新的 duplicates/triplicates

Question

我有一个数组，想知道哪些是 duplicate/triplicate 或更多。

示例：仅当出现 3 次或更多次时才获取最新商品。

输入：

const items = [
  {id: 3, date: new Date('2020/8/3')},
  {id: 1, date: new Date('2020/8/1')},
  {id: 1, date: new Date('2020/8/4')},
  {id: 1, date: new Date('2020/8/2')},
  {id: 2, date: new Date('2020/8/1')},
  {id: 2, date: new Date('2020/8/4')},
  {id: 3, date: new Date('2020/8/3')},
  {id: 3, date: new Date('2020/8/4')},
  {id: 1, date: new Date('2020/8/3')},
]

现在 id 1 出现了 4 次，id 2 出现了 2 次，id 3 出现了 3 次。我要最新的id 1和最新的id 3.

输出：

const frequentItems = [
  {id: 3, date: new Date('2020/8/4')},
  {id: 1, date: new Date('2020/8/4')},
]

你知道最简单、最简单、最有效的方法吗？

Answer 1

您可以循环两次遍历项目：第一次记住每个项目的计数（在下面代码中的对象 counts 中）并记住每个项目的最新计数（对象 latest） , 第二次只收集那些计数超过两次的。

let counts = {};
let latest = {};
for(let x of items) {
    if(!counts[x.id]) counts[x.id] = 0;
    counts[x.id]++;
    if(!latest[x.id] || latest[x.id].date < x.date) latest[x.id] = x;
}

let frequentItems  = [];
for(let id in counts) {
    if(counts[id] > 2) frequentItems.push(latest[id]);
}

Answer 2

您还可以利用 Set

根据定义does/should不包含重复项目。

创建一个新集

let dataSet = new Set()

2.Iterate遍历数据并将item的id加入集合

dataSet.add(item.id)

生成的数据集将包含唯一的 ID

Answer 3

最好的运行时间是 O(n)，即使用类似 count sort 的算法和少量 O(n) 的额外内存 space；查看下面的代码片段

const items = [
  {id: 3, date: new Date('2020/8/3')},
  {id: 1, date: new Date('2020/8/1')},
  {id: 1, date: new Date('2021/8/2')},
  {id: 2, date: new Date('2020/8/1')},
  {id: 2, date: new Date('2020/8/4')},
  {id: 3, date: new Date('2022/8/3')},
  {id: 3, date: new Date('2020/8/4')},
  {id: 1, date: new Date('2020/8/3')},
];

// used to keep track of repetition number of each id;
const itemCount = Object.create(null);
// used to random access each object by its key later;
const keyIndexedObjects = Object.create(null);

items.forEach( item => {
  const currentItemDate = new Date( item.date );
  const prevoiusItemDate = new Date( (keyIndexedObjects[item.id]||{}).date);

  // only update key index object if its date is bigger than prevoius date
  if(!(prevoiusItemDate &&
  (prevoiusItemDate > currentItemDate))){
    keyIndexedObjects[item.id] = item;
  }
  
  itemCount[item.id] = (itemCount[item.id] || 0) + 1;
});

const desiredOutput = [];

for ( const [key, value] of Object.entries(itemCount) ){
  if( value >= 3 ) desiredOutput.push(keyIndexedObjects[key])
}

console.log(desiredOutput)

从数组中获取最新的 duplicates/triplicates

Get the latest duplicates/triplicates from array

javascript

arrays

algorithm

reduce