从阵列中获取唯一值的最快方法？

Question

我有这样的数组

students = [{name: 'Abbey', age: 25}, {name: 'Brian', age: 45},
            {name: 'Colin', age: 25}, {name: 'Dan', age: 78}]

我想要输出;

uniqueAges = [45, 78]

要明确的是,如果学生数组中出现多次出现的年龄值,我不希望在uniqueAges数组中有任何具有该年龄的对象.'Abbey'和'Colin'的年龄相同,所以他们都出去了.

我知道我可以做这样的事情然后跑 uniqueAgeGetter(students)

   function uniqueAgeGetter(list){
   var listCopy = list.slice();
   var uniqueAges = list.slice();
   for (var i = list.length - 1; i >= 0; i--) {
        for (var j = listCopy.length - 1; j >= 0; j--) {
            if(listCopy[j].name !== list[i].name && 
                listCopy[j].age == list[i].age){
                  uniqueAges.splice(i, 1)
                }   
            }
    }
   console.log(uniqueAges)
   return uniqueAges
 }

但是没有第二个循环可以做到吗？我不是时间复杂度的专家,但我试图找到这个任务是否可能是O(n).

编辑:我不是问是否uniqueAgeGetter要重写以更好地阅读或使用map,reduce或filter等功能(因为我的理解是它们最终也是一个循环).

我的问题是,uniqueAgeGetter能否以减少时间复杂度的方式进行重构？只用一个循环就可以完成吗？

谢谢.

Answer 1

This can be done in O(n) time by counting the number of times an age has been seen, and filtering out the ages with a count more than one.

Since ages have reasonable limits, we can use an integer array of length equal to the maximum possible age to store the age counts. In the example below, I take the maximum possible age to be a comfortable 200.

var students = [
  {name: 'Abbey', age: 25 }, 
  {name: 'Brian', age: 45 },
  {name: 'Colin', age: 25 }, 
  {name: 'Dan', age: 78 }
];

var studentAges = students.map(val => val.age);
var ageCounts = Array(200).fill(0);

studentAges.forEach(age => ageCounts[age] += 1);

var uniqueAges = studentAges.filter(age => ageCounts[age] == 1);

console.log(uniqueAges);

Answer 2

• 第一个想法，我们可以分两步完成：

  第一步：对数组进行排序

  ——有很多算法可以做到这一点。据我所知，目前最好的算法的复杂度是O(Nlog(N))，其中N是数组的数量。

  Step2：删除重复元素

  -- 此步骤的复杂度为 O(N) 因此，经过两个步骤，复杂度为 O(N) + O(Nlog(N))。最后，复杂度为O(Nlog(N))

• 第二个想法

  这也有 O(Nlog(N)) 的复杂性，但下次你想要获得唯一的年龄时，它将是 O(N) 。

  您可以通过一些自定义在二叉搜索树中重建，而不是将数据保存在数组中。这棵树中的这个节点将保存所有具有相同年龄的元素。

  第一次构建树的复杂度是 O(Nlog(N))

对于复杂度为O(N)的算法，目前我认为还没有技术可以解决它。：D