【Day 85 】2023-05-09 - 215. 数组中的第 K 个最大元素

[azl397985856]

215. 数组中的第 K 个最大元素

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

前置知识

• 堆
• 排序

  题目描述

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

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明:

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

[aswrise]

class Solution:
    def findKthLargest(self, nums, k):

        def quickSort(nums,l,r):
            if l < r :    
                index = partitionK(nums,l,r)
                if k-1 == index:return
                elif index > k-1:
                    quickSort(nums,l,index-1)
                else:
                    quickSort(nums,index+1,r)

        def partitionK(nums,l,r):
            tmp = nums[l]
            while l<r:
                while nums[r] <= tmp and l<r:
                    r -= 1
                nums[l] = nums[r]
                while nums[l] >= tmp and l<r:
                    l += 1
                nums[r] = nums[l]
            nums[l] = tmp
            return l
        def findK(nums):
            quickSort(nums,0,len(nums)-1)
        findK(nums) 
        return nums[k-1]

[Zoeyzyzyzy]

public int findKthLargest(int[] nums, int k) {

    final PriorityQueue<Integer> pq = new PriorityQueue<>();
    for(int val : nums) {
        pq.offer(val);

        if(pq.size() > k) {
            pq.poll();
        }
    }
    return pq.peek();
}

[lp1506947671]

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        size = len(nums)

        h = []
        for index in range(k):
            # heapq 默认就是小顶堆
            heapq.heappush(h, nums[index])

        for index in range(k, size):
            if nums[index] > h[0]:
                heapq.heapreplace(h, nums[index])
        return h[0]

时间复杂度：O(n * logk) , n is array length

空间复杂度：O(k)

跟排序相比，以空间换时间。

[LIMBO42]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        ans = -1

        def partition(nums, l, r) -> int:
            tmp_r = r
            pivot = nums[r]

            while l < r:
                while l < r and nums[l] <= pivot:
                    l = l + 1
                while l < r and nums[r] >= pivot:
                    r = r - 1
                nums[r], nums[l] = nums[l], nums[r]

            nums[l], nums[tmp_r] = pivot, nums[l]
            return l

        def quicksort(nums, l, r, t):
            nonlocal ans
            if l == r and t == l:
                ans = nums[l]
                return
            if l > r:
                return
            index = partition(nums, l, r)
            # print(index)
            # print(nums)
            if index == t:
                ans = nums[index]
                return
            elif index > t:
                quicksort(nums, l, index - 1, t)
            else:
                quicksort(nums, index + 1, r, t)

        n = len(nums)
        quicksort(nums, 0, n-1, n-k)
        return ans

[huizsh]

class Solution {

public int findKthLargest(int[] nums, int k) {

    PriorityQueue<Integer> pq = new PriorityQueue<>();

    for (int num : nums) {

        if (pq.size() < k)
            pq.offer(num);
        else if (pq.peek() < num) {

            pq.poll();
            pq.offer(num);
        }
    }

    return pq.peek();
}

}

[Diana21170648]

思路

可以直接从大到小排序，取第k个数，数字多了时间复杂度高 或从小到大排序，取第size-k个数 用小顶堆，空间换时间，k次出堆操作，堆顶元素即为所求

import heapq
from typing import List
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n=len(nums)

        h = []
        for index in range(k):
            heapq.heappush(h,nums[index])
        for index in range(k,n):
            if nums[index]>h[0]:
                heapq.heapreplace(h,nums[index])
        return h[0]

**复杂度分析**
- 时间复杂度：O(Nlogk)，其中 N 为数组长度。
- 空间复杂度：O(k)，空间换时间

[zhangyu1131]

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 小顶堆
        int n = nums.size();
        if (n < k)
        {
            return -99999;
        }
        vector<int> heap(k, 0);
        for (int i = 0; i < k; ++i)
        {
            heap[i] = nums[i];
        }
        make_heap(heap.begin(), heap.end(), greater<int>()); // 小顶堆
        for (int i = k; i < n; ++i)
        {
            if (nums[i] > heap[0])
            {
                pop_heap(heap.begin(), heap.end(), greater<int>());
                heap.pop_back();
                heap.push_back(nums[i]);
                push_heap(heap.begin(), heap.end(), greater<int>());
            }
        }

        return heap[0];
    }
};

[Abby-xu]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        #/ heap: O(N)[creat heap] + O(klogN)[pop k times] 
        #/ where k <= N -> worst case: O(NlogN)
        ### quick select (quick sort) time: O(N) 
        ### select the right most element as pivot
        # nums.sort()
        # return nums[len(nums) - k]
        from random import randint

        def partition(p, r):
            pivot_index = randint(p, r)
            # Move value of pivot to the end
            nums[pivot_index], nums[r] = nums[r], nums[pivot_index]

            pivot = nums[r] ## pivot 最右
            i = p - 1

            for j in range(p, r):
                if nums[j] <= pivot:
                    i = i + 1
                    nums[i], nums[j] = nums[j], nums[i]
            i = i + 1
            nums[i], nums[r] = nums[r], nums[i]
            return i

        def smallest(p, q, K):
            if p == q:
                return nums[p]

            r = partition(p, q)
            if r == K:
                return nums[r]

            if r > K:
                # search the lower half
                return smallest(p, r - 1, K)
            else:
                # search the upper half
                return smallest(r + 1, q, K)

         # kth largest is (len(nums) - k)th smallest 
        return smallest(0, len(nums) - 1, len(nums) - k)

[bookyue]

    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        int start = 0;
        int end = nums.length - 1;

        int pivot = partition(nums, start, end);
        while (target != pivot) {
            if (pivot > target)
                end = pivot - 1;
            else
                start = pivot + 1;

            pivot = partition(nums, start, end);
        }

        return nums[pivot];
    }

    private int partition(int[] nums, int left, int right) {
        if (left == right) return right;

        int mid = left + (right - left) / 2;
        if (nums[left] > nums[mid]) swap(nums, left, mid);
        if (nums[left] > nums[right]) swap(nums, left, right);
        if (nums[mid] > nums[right]) swap(nums, mid, right);
        swap(nums, left, mid);

        int pivot = nums[left];
        int lo = left + 1;
        int hi = right;

        while (true) {
            // while (lo <= right && nums[lo] < pivot) lo++;
            // while (hi > left && nums[hi] > pivot) hi--;
            // while (nums[hi] > pivot) hi--;
            while (nums[lo] < pivot) lo++;
            while (nums[hi] > pivot) hi--;
            if (lo >= hi) break;

            swap(nums, lo++, hi--);
        }

        swap(nums, left, hi);
        return hi;
    }

    private void swap(int[] nums, int i, int j) {
        if (i == j) return;

        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

[wangqianqian202301]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_select(nums, k, start, end):
            l, r = start, end
            mid = l + (r - l) // 2
            pivot = nums[mid]
            while l <= r:
                while l <= r and nums[l] > pivot:
                    l += 1
                while l <= r and nums[r] < pivot:
                    r -= 1

                if l <= r:
                    nums[l], nums[r] = nums[r], nums[l]
                    l += 1
                    r -= 1
            if start + k - 1 <= r:
                return quick_select(nums, k, start, r)
            if start + k - 1 >= l:
                return quick_select(nums, k - (l - start), l, end)
            return nums[r + 1]
        return quick_select(nums, k, 0, len(nums) - 1)

[harperz24]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        minheap = nums[:k]
        heapq.heapify(minheap)

        for num in nums[k:]:
            if num > minheap[0]:
                heapq.heappushpop(minheap, num)

        return minheap[0]

[snmyj]

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        for(auto x:nums) pq.push(x);
        for(int i=0;i<nums.size()-k-1;i++){
            pq.pop();
        }
        return pq.top();

    }
};

[JasonQiu]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def partition(left, right):
            pivot = nums[left]
            k = left
            for i in range(left + 1, right + 1):
                if nums[i] < pivot:
                    k += 1
                    nums[k], nums[i] = nums[i], nums[k]
            nums[left], nums[k] = nums[k], nums[left]
            return k

        left, right = 0, len(nums) - 1
        while True:
            index = partition(left, right)
            if index == len(nums) - k:
                return nums[index]
            if index > len(nums) - k:
                right = index - 1
            else:
                left = index + 1

[Hughlin07]

class Solution {

public int findKthLargest(int[] nums, int k) {
     PriorityQueue<Integer> pq = new PriorityQueue<>();
    for(int x: nums){
        pq.add (x);
        if(k < pq.size()){
            pq.poll();
        }
    }

    return pq.peek();
}

}

[RestlessBreeze]

code

class Solution {
public:
    void heapinsert(vector<int>& heap, int cursize, int num)
    {
        heap[cursize + 1] = num;
        int child = cursize + 1;
        int parent = child / 2;
        for (; parent >= 1; parent = child / 2)
        {
            if (heap[parent] >= heap[child])
                break;
            else
            {
                swap(heap[parent], heap[child]);
                child = parent;
            }
        }
    }

    void heapdelete(vector<int>& heap, int cursize)
    {
        swap(heap[1], heap[cursize]);
        int parent = 1;
        int child;
        for (; parent <= (cursize - 1) / 2; parent = child)
        {
            child = parent * 2;
            if (child + 1 <= cursize - 1 && heap[child + 1] > heap[child])
                child++;
            if (heap[parent] >= heap[child])
                break;
            else
                swap(heap[parent], heap[child]);
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        vector<int> heap(nums.size() + 1);
        int cursize = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            heapinsert(heap, cursize, nums[i]);
            cursize++;
        }   
        for (int i = 0; i < k; i++)
        {
            heapdelete(heap, cursize);
            cursize--;
        }    
        return heap[heap.size() - k];
    }
};

[kangliqi1]

class Solution {

int count = 0;

public int findKthLargest(int[] nums, int k) {

    int[] heap = new int[k + 1];
    for (int num: nums)
        add(heap, num, k);
    return heap[1];
}

public void add(int[] heap, int elem, int k) {

    if (count == k && heap[1] >= elem)
        return;

    if (count == k && heap[1] < elem) {

        heap[1] = heap[count--];
        siftDown(heap, k, 1);
    }

    heap[++count] = elem;
    siftUp(heap, count);
}

public void siftUp(int[] heap, int index) {

    while (index > 1 && heap[index] <= heap[index / 2]) {

        exch(heap, index, index / 2);
        index /= 2;
    }
}

public void siftDown(int[] heap, int k, int index) {

    while (index * 2 <= k) {

        int j = index * 2;

        if (j < k && heap[j] > heap[j + 1])
            j++;

        if (heap[index] < heap[j])
            break;

        exch(heap, index, j);
        index = j;
    }
}

public void exch(int[] heap, int x, int y) {

    int temp = heap[x];
    heap[x] = heap[y];
    heap[y] = temp;
}

}

[FireHaoSky]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def maxHeapify(arr, i, end):
            j = 2*i + 1
            while j <= end:
                if j+1 <= end and arr[j+1] > arr[j]:
                    j += 1
                if arr[i] < arr[j]:
                    arr[i], arr[j] = arr[j], arr[i]
                    i = j
                    j = 2*i + 1
                else:
                    break

        def maxHepify(arr, i, end):     # 大顶堆
            j = 2*i + 1                 # j为i的左子节点【建堆时下标0表示堆顶】
            while j <= end:             # 自上而下进行调整
                if j+1 <= end and arr[j+1] > arr[j]:    # i的左右子节点分别为j和j+1
                    j += 1                              # 取两者之间的较大者

                if arr[i] < arr[j]:             # 若i指示的元素小于其子节点中的较大者
                    arr[i], arr[j] = arr[j], arr[i]     # 交换i和j的元素，并继续往下判断
                    i = j                       # 往下走：i调整为其子节点j
                    j = 2*i + 1                 # j调整为i的左子节点
                else:                           # 否则，结束调整
                    break

        n = len(nums)

        # 建堆【大顶堆】
        for i in range(n//2-1, -1, -1):         # 从第一个非叶子节点n//2-1开始依次往上进行建堆的调整
            maxHepify(nums, i, n-1)

        # 排序：依次将堆顶元素（当前最大值）放置到尾部，并调整堆
        # k-1次重建堆（堆顶元素），或 k次交换到尾部（倒数第k个元素）
        for j in range(n-1, n-k-1, -1):
            nums[0], nums[j] = nums[j], nums[0]     # 堆顶元素（当前最大值）放置到尾部j
            maxHepify(nums, 0, j-1)                 # j-1变成尾部，并从堆顶0开始调整堆

        return nums[-k]

[linlizzz]

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        size = len(nums)

        h = []
        for index in range(k):
            heapq.heappush(h, nums[index])

        for index in range(k, size):
            if nums[index] > h[0]:
                heapq.heapreplace(h, nums[index])
        return h[0]

[Lydia61]

215. 数组中的第K个最大元素

思路

大根堆排序

代码

class Solution {
public:
    void maxHeapify(vector<int>& a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

    void buildMaxHeap(vector<int>& a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};

[61hhh]

代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 优先级队列构建大根堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, (a, b) -> b - a);
        for (int num : nums) {
            maxHeap.offer(num);
        }
        // 弹出前K-1个大元素
        for (int i = 0; i < k - 1; i++) {
            maxHeap.poll();
        }
        return maxHeap.peek();
    }
}

复杂度分析

• 时间复杂度：O(Nlogk)
• 空间复杂度：O(k)

[NorthSeacoder]

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    // const _nums = nums.splice(0,k);
    const heap = new MinHeap([]);
    for (let i = 0; i < nums.length; i++) {
        if (i >= k) {
            const top = heap.getHeapTop();
            if (nums[i] > top) {
                //当前值大于堆顶元素时,推出堆顶,并入堆,
                heap.pop();
                heap.push(nums[i]);
            }
        } else {
            heap.push(nums[i]);
        }
    }

    return heap.getHeapTop()
};
class MinHeap {
    constructor(arr) {
        this.heap = [0, ...arr];
        this.heap[0] = this.heap.length - 1;
        for (let i = 1; i < this.heap.length; i++) {
            this.shiftDown(i)
        }
    }

    getHeapTop() {
        return this.heap[1]
    }

    getMinChild(i) {
        if (2 * i + 1 > this.heap.length - 1) return 2 * i;
        if (this.heap[2 * i] > this.heap[2 * i + 1]) return 2 * i + 1;
        return 2 * i;
    }

    //上浮=>小->上
    shiftUp(i) {
        while (i >> 1 > 0) {
            let parentI = i >> 1;
            //当前节点小于父节点时交换节点
            if (this.heap[i] < this.heap[parentI]) [this.heap[i], this.heap[parentI]] = [this.heap[parentI], this.heap[i]];
            i = parentI
        }
    }
    //下沉=>大->下
    shiftDown(i) {
        while (2 * i <= this.heap.length - 1) {
            const minChild = this.getMinChild(i);
            //根节点大于最小子节点时;
            if (this.heap[i] > this.heap[minChild]) [this.heap[i], this.heap[minChild]] = [this.heap[minChild], this.heap[i]];
            i = minChild
        }
    }

    push(val) {
        this.heap.push(val);
        this.heap[0]++;
        this.shiftUp(this.heap.length - 1);
    }

    pop() {
        let res = null
        if (this.heap.length > 1) {
            res = this.heap[1];
            this.heap[1] = this.heap[this.heap.length - 1]
            this.heap.pop();
            this.heap[0]--;
            this.shiftDown(1);
        }
        return res
    }
}

[Jetery]

快选模板

class Solution {
public:
    int quick(vector<int> &nums, int l, int r, int k) {
        if(l >= r) return nums[l];
        int x = nums[(l + r) >> 1], i = l - 1, j = r + 1;
        while (i < j) {
            while (nums[ ++ i] < x);
            while (nums[ -- j] > x);
            if (i < j) swap(nums[i], nums[j]);
        }
        if(j - l + 1 >= k) {
            return quick(nums, l, j, k);
        } else {
            k = k - (j - l + 1);
            return quick(nums, j + 1, r, k);
        }
    }
    int findKthLargest(vector<int>& nums, int _k) {
        int n = nums.size();
        int k = n - _k + 1;
        int ans = quick(nums, 0, n - 1, k);
        return ans;
    }
};

[joemonkeylee]

并没有顺利做出。mark

function findKthLargest(nums: number[], k: number): number {
    let start = 0;
    let end = nums.length - 1;
    let target = k - 1;
    let datum = 0;
    while (start < end) {
        datum = start - 1
        const standard = nums[end]

        for (let i = start; i <= end; i++) {
            if (nums[i] >= standard) {
                datum += 1
                if (datum < i) {
                    swap(nums, i, datum)
                }
            }
        }
        if (datum === target) {
            break
        } else if (datum < target) {
            start = datum + 1;
        } else {
            end = datum - 1
        }
    }
    function swap(nums: Array<number>, i: number, j: number) {
        const temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp
    }

    return nums[target]
};

[kofzhang]

思路

堆实现，手搓

复杂度

时间复杂度：O(nlogn) 空间复杂度：O(k)

代码

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = [-inf]*(k+1)

        def duihua(pos):            
            f,m = 2*pos,2*pos+1
            t1 = inf
            t2 = inf
            if f<k+1:
                t1 = heap[f]
            if m<k+1:
                t2 = heap[m]
            if f<k+1 and m<k+1 and (heap[pos]>heap[f] or heap[pos]>heap[m]):
                if t1<t2:
                    heap[pos],heap[f]=heap[f],heap[pos]
                    duihua(f)
                else:
                    heap[pos],heap[m]=heap[m],heap[pos]
                    duihua(m)

            elif f<k+1 and heap[pos]>heap[f]:
                heap[pos],heap[f]=heap[f],heap[pos]
                duihua(f)
            else:
                return
        def append(t):
            if t>heap[1]:
                heap[1]=t
                duihua(1)
        for i in nums:
            append(i)
        return heap[1]