215. Kth Largest Element in an Array

[Tcdian]

215. Kth Largest Element in an Array

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

Example 1

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note

• 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

[Tcdian]

Solution 1 ( Divide and Conquer )

• JavaScript Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    return quickFind(nums, 0, nums.length - 1, k);
};

function quickFind(nums, left, right, target) {
    const pivotIndex = Math.floor(Math.random() * (right - left + 1) + left);
    const pivotValue = nums[pivotIndex];
    swap(nums, pivotIndex, right);
    let separator = left - 1;
    for (let i = left; i < right; i++) {
        if (nums[i] > pivotValue) {
            swap(nums, ++separator, i);
        }
    }
    swap(nums, ++separator, right);
    if (separator === target - 1) {
        return pivotValue;
    } else if (separator < target - 1) {
        return quickFind(nums, separator + 1, right, target);
    } else {
        return quickFind(nums, left, separator - 1, target);
    }
}

function swap(nums, x, y) {
    const temp = nums[x];
    nums[x] = nums[y];
    nums[y] = temp;
}

• TypeScript Solution

function findKthLargest(nums: number[], k: number): number {
    return quickFind(nums, 0, nums.length - 1, k);
};

function quickFind(nums: number[], left: number, right: number, target: number): number {
    const pivotIndex = Math.floor(Math.random() * (right - left + 1) + left);
    const pivotValue = nums[pivotIndex];
    swap(nums, pivotIndex, right);
    let separator = left - 1;
    for (let i = left; i < right; i++) {
        if (nums[i] > pivotValue) {
            swap(nums, ++separator, i);
        }
    }
    swap(nums, ++separator, right);
    if (separator === target - 1) {
        return pivotValue;
    } else if (separator < target - 1) {
        return quickFind(nums, separator + 1, right, target);
    } else {
        return quickFind(nums, left, separator - 1, target);
    }
}

function swap(nums: number[], x: number, y: number) {
    const temp = nums[x];
    nums[x] = nums[y];
    nums[y] = temp;
}

[Tcdian]

Solution 2 ( Heap )

• TypeScript Solution

class TopKHeap {
    private size: number;
    private data: number[];
    constructor(private capacity: number) {
        this.data = [];
        this.size = 0;
    }
    public enqueue(value: number) {
        if (this.size < this.capacity) {
            this.data.push(value);
            this.siftUp(this.size++);
        } else if (this.data[0] < value) {
            this.data[0] = value;
            this.siftDown(0);
        }
    }
    public front() {
        return this.data[0];
    }
    private siftDown(index: number) {
        const leftChildIndex = this.findLeftChild(index);
        const rightChildIndex = this.findRightChild(index);
        let parentIndex = index;
        if (leftChildIndex < this.size && this.data[parentIndex] > this.data[leftChildIndex]) {
            parentIndex = leftChildIndex;
        }
        if (rightChildIndex < this.size && this.data[parentIndex] > this.data[rightChildIndex]) {
            parentIndex = rightChildIndex;
        }
        if (parentIndex !== index) {
            this.swap(parentIndex, index);
            this.siftDown(parentIndex);
        }
    }
    private siftUp(index: number) {
        const parentIndex = this.findParentIndex(index);
        if (parentIndex >= 0 && this.data[parentIndex] > this.data[index]) {
            this.swap(parentIndex, index);
            this.siftUp(parentIndex);
        }
    }
    private findParentIndex(childIndex: number) {
        return (childIndex - 1) >> 1;
    }
    private findLeftChild(parentIndex: number) {
        return parentIndex * 2 + 1;
    }
    private findRightChild(parentIndex: number) {
        return parentIndex * 2 + 2;
    }
    private swap(x: number, y: number) {
        const temp = this.data[x];
        this.data[x] = this.data[y];
        this.data[y] = temp;
    }
}

function findKthLargest(nums: number[], k: number): number {
    const topKHeap = new TopKHeap(k);
    for (let i = 0; i < nums.length; i++) {
        topKHeap.enqueue(nums[i]);
    }
    return topKHeap.front();
};