请问我在LeetCode实现的findKthLargest函数时间复杂度是O(log n)吗？

首先先把你的代码贴出来方便讨论：

var findKthLargest = function(nums, k) {
    //var tmp = nums.slice();
    var iteration = 0;
    while (iteration < k) {
        var max = -Infinity;
        for (var i = 0; i < nums.length; i++) {
            var cut;
            if (nums[i] > max) {
                max = nums[i];
                cut = i;
            }
        }
        nums.splice(cut, 1);
        iteration++;
    }
    return max;
};

先说说时间复杂度的问题 #

你提到觉得这个解法是O(logn)，其实这里有点小误解哦。咱们来拆解下：

• 每次循环（一共k次）里，你都要遍历整个当前数组找最大值，第一次遍历是O(n)，第二次是O(n-1)，第三次是O(n-2)...直到第k次是O(n - k + 1)
• 把这些加起来的话，总时间复杂度是O(k*n)，如果k接近n（比如找第n大的元素，也就是最小值），那复杂度就变成O(n²)了，这比O(logn)要高不少。

为什么会误以为是O(logn)？ #

可能你是把这个思路和堆排序或者二分类的算法搞混啦～比如用最小堆维护前k大的元素，每次插入调整堆是O(logk)，总复杂度是O(nlogk)；或者用快速选择算法，平均时间复杂度是O(n)，这些才是更高效的解法。

给你几个优化方向 #

• 最小堆实现：维护一个大小为k的最小堆，遍历数组时，元素比堆顶大就替换堆顶并调整堆，最后堆顶就是第k大元素。
• 快速选择：借鉴快速排序的分区思想，每次把数组分成两部分，判断第k大元素在左还是右区间，只递归处理对应区间，平均效率很高。
• 另外，你的代码里注释掉了nums.slice()，其实最好不要直接修改原数组哦，面试里有时候会要求不修改输入，所以可以把原数组复制一份再操作。

举个最小堆的简单实现例子（JavaScript）：

var findKthLargest = function(nums, k) {
    const heap = [];
    // 构建最小堆的插入逻辑
    const pushHeap = (num) => {
        heap.push(num);
        let i = heap.length - 1;
        while (i > 0) {
            const parent = Math.floor((i - 1)/2);
            if (heap[parent] > heap[i]) {
                [heap[parent], heap[i]] = [heap[i], heap[parent]];
                i = parent;
            } else {
                break;
            }
        }
    };
    // 弹出堆顶并调整堆的逻辑
    const popHeap = () => {
        const top = heap[0];
        const last = heap.pop();
        if (heap.length > 0) {
            heap[0] = last;
            let i = 0;
            while (true) {
                const left = 2*i + 1;
                const right = 2*i + 2;
                let smallest = i;
                if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
                if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
                if (smallest !== i) {
                    [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
                    i = smallest;
                } else {
                    break;
                }
            }
        }
        return top;
    };
    for (const num of nums) {
        pushHeap(num);
        if (heap.length > k) {
            popHeap();
        }
    }
    return heap[0];
};

内容的提问来源于stack exchange，提问作者motioncity