在一个具有O(n)复杂度的Javascript对象中找到3个最大值的键?

Say you have an object such as:

假设您有一个对象，例如:

let objToCheck = {
  a: 2, 
  b: 5,
  c: 9,
  d: 33,
  e: 4,
  f: 8,
  g: 3,
  h: 10
};

How would you go about returning the keys of the three largest values in ascending order, which in this case would be: [ 'c', 'h', 'd' ], in linear time? Evidently you need to loop through the entire object once to compare all values, but I'm having troubling coming up with a solution that doesn't involve nested loops which I believe is O(n²). Here is what my solution currently looks like so far:

你会怎么去把三个最大的值按升序返回，在这个例子中是:['c'， 'h'， 'd']，在线性时间?显然你需要遍历整个对象一旦比较所有的值,但我有麻烦想出了一个解决方案,不涉及嵌套循环,我相信是O(n²)。下面是我目前的解决方案:

function findBig3(obj){
  const res = [];
  const largest = Object.values(obj).sort((a,b) => {return b-a}).slice(0,3);

  for (let key in obj){
    largest.forEach( (val) => {
      if (obj[key] === val) res.push(key);
    });
  }
  return res;
}

I would imagine you need to declare three variables, such as big1, big2, big3, and as you loop through the object do some type of comparison check and reassign as appropriate, but I'm struggling with the implementation.

我想您需要声明三个变量，比如big1、big2、big3，当您循环遍历对象时，您需要做一些类型的比较检查和重新分配，但是我正在努力实现。

3 个解决方案

#1

This algorithm runs in O(n).

这个算法在O(n)中运行。

function getThreeLargestKeys(obj){
    var k1, k2, k3;
    var v1, v2, v3;
    v1 = v2 = v3 = -Infinity;

    // O(1)
    var insertKey = function(key){
        var value = obj[key];  // note 1

        // note 2
        if(value >= v1){
            v3 = v2; v2 = v1; v1 = value;
            k3 = k2; k2 = k1; k1 = key;
        }else if(value >= v2){
            v3 = v2; v2 = value;
            k3 = k2; k2 = key;
        }else if(value >= v3){
            v3 = value;
            k3 = key;
        }
    };

    // O(n)
    for(var key in obj){
        // note 3
        insertKey(key);
    }

    return [k1, k2, k3];
}

https://jsfiddle.net/DerekL/pzatq729/

Please do not copy-paste the code right into your homework as your solution. Rewrite the code once you fully understand it.

请不要将代码复制粘贴到作业中作为解决方案。一旦完全理解了代码，就重写它。

Note:

注意:

This assumes that object lookup is O(1). This ultimately depends on how it is implemented in the interpreter, but it is usually lower than O(log n).
这假设对象查找是O(1)。这最终取决于如何在解释器中实现它，但它通常低于O(log n)。
These conditionals can certainly be optimized. I will leave that as a practice for the reader.
这些条件肯定可以优化。我把它留给读者作为练习。
Normally we should check if the key is owned by the object instance, but here I will assume that the input object is not inherited from Object.prototype.
通常，我们应该检查键是否属于对象实例，但是这里我假设输入对象不是继承自object .prototype的。

#2

you can keep pushing 3 objects in an array and keep sorting the array, assuming number of elements you need k is sufficiently less than n, this can give linear efficiency on average.

你可以一直把3个对象放在一个数组中，然后继续对数组进行排序，假设你需要的元素个数k足够小于n，这就能使平均的线性效率。

let objToCheck = {
  a: 2, 
  b: 5,
  c: 9,
  d: 33,
  e: 4,
  f: 8,
  g: 3,
  h: 10
};


function findBig3(obj){
  var res = [-1,-1,-1];

  for (let key in obj){
   res[3] = obj[key];
   res.sort(function(a,b){return b-a});
  }
  res.pop();
  return res;
}


console.log(findBig3(objToCheck));

#3

If you just change Object.values to Object.keys and use the key to select from the original object, you can avoid the last loop.

如果你只是改变对象。值对象。使用键和键从原始对象中选择，可以避免最后的循环。

let objToCheck = {
  a: 2,
  b: 5,
  c: 9,
  d: 33,
  e: 4,
  f: 8,
  g: 3,
  h: 10
};

function findBig3(obj){
  return Object.keys(obj).sort((a,b) => {return obj[b]-obj[a]}).slice(0,3);
}

console.log(findBig3(objToCheck));

#1