javascript - 这个的时间复杂度是多少以及如何使其为 0(n)？

Question

Leetcode问题Third Maximum Number要求一个 O(n) 的解决方案。

这是我的解决方案，它的时间复杂度是多少？以及如何使其为 0(n)？我以为 reduce 实际上是 0(n)，但也许不是？ sort 的时间复杂度是多少？

var thirdMax = function(nums) {

    var arr = nums.reduce((unique, element) =>{
        return unique.includes(element) ? unique : [...unique, element]
    }, []);     
    arr.sort(function(a, b){return b-a});
    console.log(arr);

    if(arr.length < 3){
        return arr[0];
    } else {
        return arr[2]
    }
};

谢谢!

Answer 1

reduce 迭代输入数组并检查另一个数组中的任何元素是否匹配，其复杂度为 O(N^2)(最坏情况，每个项目都必须与其他项目进行检查)。

对数组进行排序的复杂性O(N log N)。

因此，总的来说，最坏情况的复杂度是 O(N^2)。

我会在跟踪 3 个持久变量的同时进行迭代 - 迄今为止找到的最高数字、第二高的数字和第三高的数字。因为看起来他们也想禁止重复计数，所以使用 Set 来跟踪到目前为止已经看到的数字。 Set.has 是 O(1)，因此无需担心额外的复杂性:

var thirdMax = function(nums) {
  let highest = -Infinity;
  let secondHighest = -Infinity;
  let thirdHighest = -Infinity;
  const numsSeen = new Set();
  nums.forEach((num) => {
    if (numsSeen.has(num)) {
      return;
    }
    numsSeen.add(num);
    
    if (num > highest) {
      [highest, secondHighest, thirdHighest] = [num, highest, secondHighest];
    } else if (num > secondHighest) {
      [secondHighest, thirdHighest] = [num, secondHighest];
    } else if (num > thirdHighest) {
      thirdHighest = num;
    }
  });
  return thirdHighest === -Infinity
  ? highest
  : thirdHighest;
};

console.log(
  thirdMax([1, 2, 3]),
  thirdMax([1, 2, 3, 4]),
  thirdMax([2,2,3,1])
);