【Day 85 】2023-01-24 - 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 ≤ 数组的长度。

[zjsuper]

import heapq class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: lens = len(nums) h = [] for i in range(lens): heapq.heappush(h,nums[i]) if len(h) > k: heapq.heappop(h) heapq.heapify(h)

    return h[0]

[bwspsu]

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

[klspta]

class Solution {
    int M = 10010, N = 2 * M;
    int[] tr = new int[N];
    int lowbit(int x) {
        return x & -x;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }
    void add(int x) {
        for (int i = x; i < N; i += lowbit(i)) tr[i]++;
    }
    public int findKthLargest(int[] nums, int k) {
        for (int x : nums) add(x + M);
        int l = 0, r = N - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (query(N - 1) - query(mid - 1) >= k) l = mid;
            else r = mid - 1;
        }
        return r - M;
    }
}

[snmyj]

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(),nums.end());
        return nums[n-k];  
    }
};

[mayloveless]

思路

小顶堆

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    let minQ = new MinPriorityQueue();
    for (let i = 0; i < nums.length; ++i) {
        if (i<k) {
            minQ.enqueue(nums[i])
        } else {
            if (minQ.front().element <= nums[i]) {
                minQ.dequeue();
                minQ.enqueue(nums[i])
            }
        }
    }

    return minQ.front().element;
};

复杂度

时间：O((n * logk) 空间：O(k)

[Elsa-zhang]

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        h = []
        for i in range(n):
            heapq.heappush(h,-nums[i])

        for i in range(k-1):
            heapq.heappop(h)

        return -h[0]

[zywang0]

class Solution {
    int M = 10010, N = 2 * M;
    int[] tr = new int[N];
    int lowbit(int x) {
        return x & -x;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }
    void add(int x) {
        for (int i = x; i < N; i += lowbit(i)) tr[i]++;
    }
    public int findKthLargest(int[] nums, int k) {
        for (int x : nums) add(x + M);
        int l = 0, r = N - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (query(N - 1) - query(mid - 1) >= k) l = mid;
            else r = mid - 1;
        }
        return r - M;
    }
}

[RestlessBreeze]

code

class Solution {
public:
    int quickSelect(vector<int>& a, int l, int r, int index) {
        int q = randomPartition(a, l, r);
        if (q == index) {
            return a[q];
        } else {
            return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
        }
    }

    inline int randomPartition(vector<int>& a, int l, int r) {
        int i = rand() % (r - l + 1) + l;
        swap(a[i], a[r]);
        return partition(a, l, r);
    }

    inline int partition(vector<int>& a, int l, int r) {
        int x = a[r], i = l - 1;
        for (int j = l; j < r; ++j) {
            if (a[j] <= x) {
                swap(a[++i], a[j]);
            }
        }
        swap(a[i + 1], a[r]);
        return i + 1;
    }

    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0));
        return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
    }
};

[bookyue]

code

    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 (pivot != target) {
            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) >>> 1;
        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 (nums[lo] < pivot) lo++;
            while (nums[hi] > pivot) hi--;

            if (lo >= hi) break;
            swap(nums, lo, hi);
            lo++;
            hi--;
        }

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

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

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

[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;
    }
};

[tiandao043]

思路

一眼望去以为快排，看了题解发现是堆

代码

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> pq;
        for(auto n:nums){
            if(pq.size()==k && pq.top() >= n)continue;
            if(pq.size()==k){
                pq.pop();
            }
            pq.push(n);
        }
        return pq.top();
    }
};

倒着装

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {

        priority_queue<int, vector<int>, less<int>> big_heap;
        for(int i = 0; i < nums.size(); ++i)
            big_heap.push(nums[i]);

        for(int i = 0; i < k-1; ++i)
            big_heap.pop();
        return big_heap.top();
    }
};

[FlipN9]

/**
    Approach 1: Quick Select

    TC: O(N)    SC: O(logN)
*/
class Solution {
    Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        // if (nums.length == 0 || k == 0) return 0;
        k = nums.length - k;
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    private int quickSelect(int[] arr, int left, int right, int k) {
        int idx = partition(arr, left, right);
        if (idx == k) 
            return arr[k];
        else if (idx > k) 
            return quickSelect(arr, left, idx - 1, k);
        else 
            return quickSelect(arr, idx + 1, right, k);
    }

    /**
        经过每次 partition 后, 我们可以确定一个元素 pivot 的最终位置 为 q
        A[ left  ... q - 1] 的每个元素 <= pivot
        A[ q + 1 ... right - 1] 的每个元素 >= pivot
    */
    private int partition(int[] arr, int left, int right) {
        int pivotIdx = left + random.nextInt(right - left + 1);
        int pivot = arr[pivotIdx];

        int start = left;
        int end = right - 1;

        swap(arr, pivotIdx, right);
        while (start <= end) {
            if (arr[start] < pivot) {
                start++;
            } else if (arr[end] > pivot) {
                end--;
            } else {
                swap(arr, start++, end--);
            }
        }
        swap(arr, start, right);
        return start;
    }

    private void swap(int[] arr, int l ,int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
}

[whoam-challenge]

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

    def partition(arr: List[int], low: int, high: int) -> int:
        pivot = arr[low]                                        # 选取最左边为pivot

        left, right = low, high     # 双指针
        while left < right:

            while left<right and arr[right] >= pivot:          # 找到右边第一个<pivot的元素
                right -= 1
            arr[left] = arr[right]                             # 并将其移动到left处

            while left<right and arr[left] <= pivot:           # 找到左边第一个>pivot的元素
                left += 1
            arr[right] = arr[left]                             # 并将其移动到right处

        arr[left] = pivot           # pivot放置到中间left=right处
        return left

    def randomPartition(arr: List[int], low: int, high: int) -> int:
        pivot_idx = random.randint(low, high)                   # 随机选择pivot
        arr[low], arr[pivot_idx] = arr[pivot_idx], arr[low]     # pivot放置到最左边
        return partition(arr, low, high)                        # 调用partition函数

    def topKSplit(arr: List[int], low: int, high: int, k: int) -> int:
        # mid = partition(arr, low, high)                   # 以mid为分割点【非随机选择pivot】
        mid = randomPartition(arr, low, high)               # 以mid为分割点【随机选择pivot】
        if mid == k-1:                                      # 第k小元素的下标为k-1
            return arr[mid]                                 #【找到即返回】
        elif mid < k-1:
            return topKSplit(arr, mid+1, high, k)           # 递归对mid右侧元素进行排序
        else:
            return topKSplit(arr, low, mid-1, k)            # 递归对mid左侧元素进行排序

    n = len(nums)
    return topKSplit(nums, 0, n-1, n-k+1)                   # 第k大元素即为第n-k+1小元素