代码之家 › 专栏 › 技术社区 › motioncity

我在网上找到的这个函数的时间复杂度是O(n)?

time-complexity javascript

motioncity · 技术社区 · 8 年前

我正在努力 this problem on LeetCode ,以下是我在网上找到的解决方案:

//  use quick select
var findKthLargest = function(nums, k) {
    var smaller = [];
    var larger = [];
    var pivot = nums[parseInt(nums.length/2)];
    var pivotCnt = 0;

    for (var i = 0; i < nums.length; i++) {
        var num = nums[i];      
  
        if(num > pivot) {
            larger.push(num);
        }
        else if(num < pivot) {
            smaller.push(num);
        }
        else {
            pivotCnt++;
        }
    }
  
    if (k <= larger.length) { // if larger includes k
        return findKthLargest(larger, k);
    }
    else if (k - larger.length - pivotCnt <= 0) { // k is part of pivot
        return pivot;
    }
    else { // if smaller inclues k
        return findKthLargest(smaller, k - larger.length - pivotCnt);
    }
};

现在我相信这是一个O(n)解决方案,因为最坏的情况是我们遍历整个数组,但我不确定。