azl397985856 commented 2 years ago

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 ≤ 数组的长度。

yanglr commented 2 years ago

思路

可以直接sort, 也可以用堆排序来做。这里我们使用堆排序来实现。

根据test case的测试发现 1 <= k <= nums.length, 即k总是处于合法范围, 不会超过nums数组的长度。

方法: 堆排序

先把nums数组中的元素都放进大顶堆, 然后弹出k-1个数, 此时再取优先队列的top值即为所求。

代码

实现语言: C++

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int res;
        priority_queue<int> q;
        for (auto& num : nums)
            q.push(num);

        while (!q.empty() && k > 1)
        {
            auto top = q.top();            
            q.pop();
            k--;
        }
        res = q.top();
        return res;
    }
};

复杂度分析

时间复杂度：O(N logN), 主要取决于堆排序的复杂度
空间复杂度：O(N), 优先队列使用了O(n)的额外空间

ZacheryCao commented 2 years ago

Idea:

Heap. If heap.length < k, push current element into heap. If heap.length >= k and current element is larger than heap's first element, push current element into heap and pop out heap's first element.

Code:

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for i in nums:
            if len(heap) < k:
                heapq.heappush(heap, i)
            else:
                if i > heap[0]:
                    heapq.heappush(heap, i)
                    heapq.heappop(heap)
        return heap[0]

Complexity:

Time: O(N log K). Build heap is O(K log K). Heappop and heappush is O(log K). Space: O(K)

biancaone commented 2 years ago

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        if not nums or k < 1 or k > len(nums):
            return -1

        return self.quick_select(nums, 0, len(nums) - 1, k)

    def quick_select(self, nums, start, end, k):
        if start == end:
            return nums[start]

        i, j = start, end
        pivot = nums[(i + j) // 2]

        while i <= j:
            while i <= j and nums[i] > pivot:
                i += 1
            while i <= j and nums[j] < pivot:
                j -= 1

            if i <= j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1

        # start, j, i, end        
        if k <= j - start + 1:
            return self.quick_select(nums, start, j, k)

        if k >= i + 1 - start:
            # i - start is the total number of elements before index i
            return self.quick_select(nums, i, end, (k - (i - start)))

        return nums[j + 1]

falconruo commented 2 years ago

思路: 方法一、排序方法二、小顶堆

复杂度分析: 方法一、时间复杂度: O(nlogn)，其中n是数组nums的长度空间复杂度: O(logn)

方法二、时间复杂度: O(n + klogk)，其中n是数组nums的长度空间复杂度: O(logk)

代码(C++):

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();

        priority_queue<int, vector<int>, greater<int>> pq;

        int len = 0;

        for (auto num : nums) {
            if (len < k) {
                pq.push(num);
            } else if (pq.top() < num) {
                pq.pop();
                pq.push(num);
            }
            len++;
        }

        return pq.top();
    }
};

zhangzz2015 commented 2 years ago

思路

解决最大的前k个元素，有几种方法，大顶堆，小顶堆，有时候如果有多个vector，会用到多路merge方法 + heap，有时候如果有局部有序，可以使用二分方法。
方法1. 当前我使用小顶堆方法，时间复杂度为O(n logk)，空间复杂度为O(k)。
方法2，使用quick select方法，注意quick select方法，尽快最快的时候为O(n)，但是最差的时候是O(n^2)，因此quick select在选择pivot上一定要使用random选择方法，这样能做到average o(n)，空间复杂度为O(1)。

关键点

代码

语言支持：C++

C++ Code:


class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        /// two method. One use min heap
        priority_queue<int, vector<int>, greater<int>> pq; 

        for(int i=0; i< nums.size(); i++)
        {
            if(pq.size()<k)
            {
                pq.push(nums[i]); 
            }
            else 
            {
                if(nums[i]> pq.top())
                {
                    pq.pop(); 
                    pq.push(nums[i]); 
                }
            }            
        }

        return pq.top();

    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        /// two method. One use min heap

        int start =0; 
        int end = nums.size()-1; 
        k--; 
        for(int i=0; i< nums.size(); i++)
        {
            //  random choose pivot. 
            // This part code is very important. It will improve running time from 40ms to 4ms. 
            int pivotIndex = rand()%(end - start+1)+ start; 
            swap(nums[start], nums[pivotIndex]); 
            //  
            int index = quickSort(nums, start, end); 

            if(index == k)
                return nums[index]; 
            else if(index < k)
            {
                start = index+1; 
            }
            else
            {
                end = index - 1; 
            }            
        }

        return INT_MIN; // assert(0); 
    }

    int quickSort(vector<int>& nums, int start, int end)
    {
        int pivot = nums[start]; 
        while(start< end)
        {
            while(start<end && nums[end]<=pivot)
            {
                end--; 
            }

            swap(nums[start], nums[end]); 

            while(start<end && nums[start]>pivot)
            {
                start++; 
            }

            swap(nums[start], nums[end]);             
        }

        nums[start] = pivot; 
        return start; 

    }
};

复杂度分析

wangzehan123 commented 2 years ago

Java Code:


class Solution {
    //使用大堆去做。
    //堆的属性：
    //底层使用数组实现，数组的索引0处留空，这样就满足了性质1：
    //性质1:索引k的节点的子节点索引,2k，2k+1，第k个节点的父亲节点：k/2
    //注意点：！！！！！！！！！千万分清索引和索引元素，要不十分容易错
    public int findKthLargest(int[] nums, int k) {
        //思路很简单，构建一个大堆，然后依次删除堆顶的数（底层操作是数组）
        //构建堆时，思路是从len/2处从右往左扫描，并对每个扫描到的元素下沉操作
        int len=nums.length;
        int[] arr=new int[len+1];
        for(int i=1;i<len+1;i++){
            arr[i]=nums[i-1];
        }
        //构建堆
        buildHeap(arr);
        //删除操作，思路：将堆顶与最后一个元素交换位置，然后忽略掉最后一个元素
        int last=arr.length-1;
        //堆排序
        while(last!=1){
            swap(arr,1,last);
            last--;
            sink(arr,1,last);
        }
        return arr[arr.length-k];

    }

    //构建堆
    public void buildHeap(int[] nums){
        int len=nums.length;
        for(int i=(len-1)/2;i>=1;i--){
            sink(nums,i,len-1);
        }

    }

    //节点tar下沉操作,步骤：找到左右子节点的大节点（右节点可能不存在），与顶点比较
    public void sink(int[] nums,int k,int range){
        //最大索引位置,是可以变化的
        while(k*2<=range){//判定是不是超过最大值（很巧妙）
            int lft=2*k;
            int rgt=2*k+1;
            //找到左右子节点的大节点索引
            int max=lft;
            if(rgt<=range){
                //右节点存在
                if(nums[rgt]>nums[lft]){
                    max=rgt;
                }
            }
            if(nums[max]>nums[k]){
                swap(nums,max,k);
            }
            k=max;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!精髓，实则循环替换了递归
        }
    }

    public void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}

AgathaWang commented 2 years ago

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

wenjialu commented 2 years ago

idea

堆排序。排成大顶堆，数组变成从小到大的顺序。取nums[-k] 就是第k大元素

code

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # i: parent.
        def beHeap(nums, i, length):
            # child
            k = 2 * i + 1
            while k <= length:
                if k + 1 <= length and nums[k + 1] > nums[k]:
                    k = k + 1
                if nums[k] > nums[i]: # chile node larger than parent node.
                    nums[k], nums[i]  = nums[i] ,nums[k] 
                    i = k                    
            k = 2 * i + 1
                else:
                    break
        # first i should be the last parent = len(nums)/2 - 1
        n = int(len(nums) / 2 - 1)
        # print(n)
        # form a heap   
        for i in range(n, -1, -1): # 从下到上找。
            beHeap(nums, i, len(nums) - 1)
        # print(nums)    
        # take the top to the end of the array. keep form a heap.
        for i in range(len(nums) - 1, -1, -1):
            nums[0], nums[i] = nums[i], nums[0]
            beHeap(nums, 0, i - 1)
        return nums[-k]

complexity

时间复杂度：O(nlogn)，建堆的时间代价是 O(n)，删除的总代价是 O(klogn)？？，因为 k < n，故渐进时间复杂为 O(n + k log n) = O(nlogn)。空间复杂度：O(\log n)O(logn)，即递归使用栈空间的空间代价

skinnyh commented 2 years ago

Note

Use a min heap. Add new num into heap when heap size is less than k. When the size reaches k, replace the heap top when new num is larger than the top. So we maintain the heap top as the smallest one among the top k large numbers.

Solution

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for n in nums:
            if len(heap) < k:
                heapq.heappush(heap, n)
            elif n > heap[0]:
                heapq.heapreplace(heap, n)
        return heap[0]

Time complexity: O(NlogK)

Space complexity: O(K)

pophy commented 2 years ago

思路1 - PQ/min heap

把数字依次放入最小堆，如果堆大小大于K 则弹出堆顶最小值
最后返回堆顶元素

Java Code

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
            queue.add(nums[i]);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        return queue.peek();
    }

时间&空间

时间 O(nlog(k))
空间 O(k)

思路2 - 快速排序partition

利用快速排序的partition，可以找到一个排序正确的数，他在排序正确的数组中位置为Index
- 如果index > target index 则在数组前部重新Partition，即 end = index - 1
- index < target index, 则 start = index + 1
- index == target index 返回答案

Java Code

public class KthLargestNumber {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int targetIndex = n - k;
        int start = 0, end = n - 1;
        while (true) {
            int index = partition(nums, start, end);
            if (index == targetIndex) {
                return nums[targetIndex];
            } else if (index > targetIndex) {
                end = index - 1;
            } else {
                start = index + 1;
            }
        }
    }
    private int partition(int[] nums, int start, int end) {
        int pivot = start, l = start + 1, r = end;
        while (l <= r) {
            if (nums[l] > nums[pivot] && nums[r] < nums[pivot]) {
                swap(nums, l, r);
                l++;
                r--;
            }
            if (nums[l] <= nums[pivot]) {
                l++;
            }
            if (nums[r] >= nums[pivot]) {
                r--;
            }
        }
        swap(nums, pivot, r);
        return r;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

时间&空间

时间 O(log(n))
空间 O(1）

Laurence-try commented 2 years ago

思路

priority queue

代码

使用语言：Python 3

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

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

Daniel-Zheng commented 2 years ago

思路

排序。

代码(C++)

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.rbegin(), nums.rend());
        return nums[k - 1];
    }
};

复杂度分析

时间复杂度：O(NLogN)
空间复杂度：O(1)

mannnn6 commented 2 years ago

代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }

    public void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    public void maxHeapify(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, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

复杂度

时间复杂度：O(NLogN) 空间复杂度：O(logN)

yan0327 commented 2 years ago

Go的堆排序，关键是要注意type Iheap 而不能用 type heap!!!

type Iheap []int
func(h Iheap)Len()int{return len(h)}
func(h Iheap)Less(i,j int) bool{return h[i]>h[j]}
func(h Iheap)Swap(i,j int) {h[i],h[j] = h[j],h[i]}
func(h *Iheap) Push(x interface{}) {
    *h = append(*h,x.(int))
}
func(h *Iheap) Pop() interface{}{
    x := *h
    out := x[len(x)-1]
    *h = x[:len(x)-1]
    return out
}
func findKthLargest(nums []int, k int) int {
    if len(nums) < k{
        return 0
    }
    h := &Iheap{}
    for i:=0;i<len(nums);i++{
        heap.Push(h,nums[i])
    }
    out:=0
    for i:=0;i<k;i++{
       out = heap.Pop(h).(int)
    }
    return out
}

时间复杂度O（NlogK）空间复杂度O（N）

ymkymk commented 2 years ago

class Solution { Random random = new Random();

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

public int quickSelect(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);
    }
}

public int randomPartition(int[] a, int l, int r) { int i = random.nextInt(r - l + 1) + l; swap(a, i, r); return partition(a, l, r); }

public int partition(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, j);
        }
    }
    swap(a, i + 1, r);
    return i + 1;
}

public void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

}

okbug commented 2 years ago

var findKthLargest = function(nums, k) {
    return nums.sort((a, b) => b - a)[k - 1]
};

Toms-BigData commented 2 years ago

Golang代码215

思路

冒泡排序

代码

func findKthLargest(nums []int, k int) int {
    for i:=0;i<k;i++{
        j:=0
        for j<len(nums)-1{
            if nums[j] <= nums[j+1]{
                j++
            }else {
                nums[j], nums[j+1] = nums[j+1],nums[j]
                j++
            }
        }
    }
    return nums[len(nums)-k]
}

复杂度

时间:O(nk) 空间:O(1)

machuangmr commented 2 years ago

代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        if(len == 0) return -1;
        Arrays.sort(nums);
        return nums[len - k];
    }
}

复杂度

时间复杂度 O(nlogn)
空间复杂度 O(1)

chun1hao commented 2 years ago

var findKthLargest = function (nums, k) {
  let len = nums.length;
  let sort = function (nums, k, start = 0, end = nums.length - 1) {
    if (start < end) {
      let povite = nums[end];
      let pos = start - 1;
      for (let i = start; i <= end; i++) {
        if (nums[i] <= povite) {
          pos++;
          [nums[pos], nums[i]] = [nums[i], nums[pos]];
        }
      }
      let lastIdx = len - pos;
      if (lastIdx === k) {
        return nums[pos];
      } else if (lastIdx > k) {
        return sort(nums, k, pos + 1, end);
      } else {
        return sort(nums, k, start, pos - 1);
      }
    }
    return nums[len - k];
  };
  return sort(nums, k);
};

Zhang6260 commented 2 years ago

JAVA版本

思路：

使用构建堆来完成的（topk的问题，可以使用快速选择或者堆来完成）

class Solution {
    //使用堆排序（在java中可以使用优先队列来完成！！）
    //建立  大根堆 或者 小根堆  来完成！！！
    public int findKthLargest(int[] arr, int k) {
        return fun(arr,k);
    }
    private int  fun(int[]arr,int k){
        // 1.构建小根堆
        for(int i=arr.length/2 -1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adujust(arr,i,arr.length);
        }
        //调整堆结构  交换对顶元素 与 末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);
            adujust(arr,0,j);
        }
        return arr[k-1];
    }
    private void adujust(int[] arr,int i,int length){
        int temp =arr[i];
        for(int k=i*2 +1;k<length;k=2*k+1){
            if(k+1<length&&arr[k]>arr[k+1]){
                k++;
            }
            if(arr[k]<temp){
                arr[i] = arr[k];
                i = k;
            }else {
                break;
            }
        }
        arr[i] = temp;
    }
    private  void swap(int[] arr, int i, int j) {
        int temp  = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

时间复杂度：O(nlogn)

空间复杂度：O(1)

chenming-cao commented 2 years ago

解题思路

堆。建立小顶堆储存k个元素。遍历数组，前k个元素放入堆中，从第k+1个元素开始，比较当前元素和堆顶元素。如果当前元素小于等于堆顶元素，当前元素不可能是第k大元素，跳过当前元素；如果当前元素大于堆顶元素，则从堆顶取出最小元素，将当前元素放入堆中。每一时刻堆中储存的都是到当前元素为止前k大的元素。当整个数组遍历结束，堆中保留的便是所有元素中前k大的元素。返回堆顶元素即为结果。

代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // use a min-heap to store k elements
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
            if (i < k) {
                heap.offer(nums[i]);
                continue;
            }
            // starting from the element with index k, we will check the element with the element from the top of the heap
            int top = heap.peek();
            // if the element is greater than the top of heap, we will poll the minimum from the heap and add this element in. if the element is no greater than the top, just ignore this element, it could not be the kth largest element
            if (nums[i] > top) {
                heap.poll();
                heap.offer(nums[i]);
            }
        }
        // return the top of the heap, which is the kth largest element
        return heap.poll();
    }
}

复杂度分析

时间复杂度：O(n*logk)，n为数组长度，每次堆的操作为O(logk)
空间复杂度：O(k)，堆的大小为k

jaysonss commented 2 years ago

思路

固定堆

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(k+1);
        int c = 0;
        for(int num : nums){
            heap.offer(num);
            c++;
            if(c==k+1){
                heap.poll();
                c=k;
            }
        }
        return heap.peek();
    }
}

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

wenlong201807 commented 2 years ago

代码块


class MinHeap {
  constructor() {
    this.heap = [];
  }
  // 交换节点位置
  swap(i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
  }
  // 获得父节点
  getParentIndex(i) {
    return (i - 1) >> 1;
  }
  // 获得左节点
  getleftIndex(i) {
    return 2 * i + 1;
  }
  // 获得右节点
  getrightIndex(i) {
    return 2 * i + 2;
  }
  // 上移
  shiftUp(index) {
    if (index === 0) return;

    const parentIndex = this.getParentIndex(index);
    if (this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index);
      this.shiftUp(parentIndex);
    }
  }
  // 下移
  shiftDown(index) {
    const leftIndex = this.getleftIndex(index);
    const rightIndex = this.getrightIndex(index);
    if (this.heap[leftIndex] < this.heap[index]) {
      this.swap(leftIndex, index);
      this.shiftDown(leftIndex);
    }
    if (this.heap[rightIndex] < this.heap[index]) {
      this.swap(rightIndex, index);
      this.shiftDown(rightIndex);
    }
  }
  // 插入
  insert(value) {
    this.heap.push(value);
    this.shiftUp(this.heap.length - 1);
  }
  // 删除堆顶
  pop() {
    // pop()方法删除数组最后一个元素并返回，赋值给堆顶
    this.heap[0] = this.heap.pop();
    // 对堆顶重新排序
    this.shiftDown(0);
  }
  // 获取堆顶
  peek() {
    return this.heap[0];
  }
  // 获取堆的大小
  size() {
    return this.heap.length;
  }
}

const findKthLargest = (nums, k) => {
  const minHeap = new MinHeap();
  for (const num of nums) {
    // 将数组元素依次插入堆中
    minHeap.insert(num);
    // 如果堆大小超过k， 开始裁员， 将堆顶(最小) 的去掉
    if (minHeap.size() > k) minHeap.pop();
  }
  // 返回堆顶，此时就是第k大的元素
  return minHeap.peek();
};

kidexp commented 2 years ago

thoughts

heap

code

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        """
        use heap
        """
        heap = []
        for num in nums:
            if len(heap) < k:
                heapq.heappush(heap, num)
            elif num > heap[0]:
                heapq.heappop(heap)
                heapq.heappush(heap, num)
        return heap[0]

Complexity

Time O(nlgk)

Space O(k)

KennethAlgol commented 2 years ago


class Solution {
    public int findKthLargest(int[] nums, int k) {
        int[] sortNums = sortInt(nums);
        return sortNums[sortNums.length - k];
    }

    public int[] sortInt(int []ints){
        for(int i = 0;i < ints.length-1;i++){
            for(int j = 0;j < ints.length-1-i;j++){
                if(ints[j] > ints[j+1]){
                    int a = ints[j];
                    ints[j] = ints[j+1];
                    ints[j+1] = a;
                }
            }
        }
        return ints;
    }
}

ginnydyy commented 2 years ago

Problem

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

Note

min heap (priority queue)

Solution

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

        int n = nums.length;

        if(n < k){
            return -1;
        }

        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(int i = 0; i < n; i++){
            if(q.size() == k){
                if(nums[i] > q.peek()){
                    q.poll();
                    q.offer(nums[i]);
                }
            }else{
                q.offer(nums[i]);
            }
        }

        return q.peek();
    }
}

Complexity

T: O(n), n is the length of nums.
S: O(k), extra space is required for the min heap.

BpointA commented 2 years ago

思路

快排

Python代码


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def qselect(nums,left,right):
            if left>right:
                return nums
            l=left
            r=right
            target=nums[left]
            while left<right:
                while left<right and nums[right]>=target:
                    right-=1
                nums[left]=nums[right]
                while left<right and  nums[left]<=target:
                    left+=1
                nums[right]=nums[left]
            nums[left]=target
            if left==len(nums)-k:
                return nums[left]
            elif left>len(nums)-k:
                return qselect(nums,l,left-1)
            else:
                return qselect(nums,left+1,r)

            return nums
        return qselect(nums,0,len(nums)-1)

user1689 commented 2 years ago

题目

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

思路

Heap, quickSelection

python3

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # time nlogk
        # space logn
        heap = []
        for num in nums:
            heapq.heappush(heap, -num)
        for _ in range(k):
            tmp = heapq.heappop(heap)
        return -tmp

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # time nlogk
        # space logn
        # 维护一个大小为k的最小堆，堆顶是这k个数里的最小的，遍历完数组后返回堆顶元素即可
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]

# [1, 2, 3, 4, 5 ,6], k = 2
# [5, 6]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def partition(low, high):
            # conercase:
            # [1,2,3,4,5,6]
            # [6,5,4,3,2,1]
            pivot = random.randint(low, high)
            nums[pivot], nums[low] = nums[low], nums[pivot]
            i, j = low, low + 1
            while j <= high:
                if nums[j] > nums[low]:
                    nums[i + 1], nums[j] = nums[j], nums[i + 1]
                    i += 1
                j += 1
            nums[low], nums[i] = nums[i], nums[low]
            return i

        def quickSort(low, high):
            while True:
                # [  ] idx==k-1 [  ]
                # 6 5 4 3 2 1
                # 0 1 2 3 4 5
                # 2thLargest:idx=2-1=1
                idx = partition(low, high)
                if idx == k - 1:
                    return nums[idx]
                elif idx < k - 1:
                    # return partition(idx + 1, high)
                    low = idx + 1
                elif idx > k - 1:
                    # return partition(low, idx - 1)
                    high = idx - 1

        return quickSort(0, len(nums) - 1)
        # return nums

复杂度分析

time n
space logn

思路

维护一个有 k 个元素的最小堆, 最后就是包含 list 中最大的 k 个元素

如果当前堆不满, 直接添加

如果堆满了, 那么这 k 个元素的最小元素在堆顶, 用堆顶元素跟新的元素 n 做对比, 如果堆顶元素比 n 小, 那么 pop 堆顶的元素, 并将新的元素 n 加入堆中

最后返回 h[0] 就是第 k 大的元素因为堆中是最大的 k 个元素, 堆顶是其中最小的元素即第 k 大元素

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

        # maintain min heap h, everytime find element bigger than heap top element
        # heappop the heap top element and push the new element in
        h = []

        for i, n in enumerate(nums):
            if len(h) < k:
                heapq.heappush(h, n)
            else:
                if n > h[0]:
                    heapq.heappop(h)
                    heapq.heappush(h, n)

        return h[0]

复杂度

时间复杂度: O(nlogn) 建堆时间代价是 O(n), 删除总代价是 O(klogn), 因为 k < n, 渐进时间复杂度为 O(n+klogn) = O(nlogn)

空间复杂度: O(k) 堆的空间复杂度

learning-go123 commented 2 years ago

思路

小顶堆

代码

语言支持：Go

Go Code:


type minPriorityQueue []int
func (pq minPriorityQueue) Len() int { return len(pq) }
func (pq minPriorityQueue) Less(i, j int) bool  { return pq[i] < pq[j] }
func (pq minPriorityQueue) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i] }
func (pq *minPriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(int)) }
func (pq *minPriorityQueue) Pop() interface{} {
    res := (*pq)[len(*pq)-1]
    *pq = (*pq)[:len(*pq)-1]
    return res
}

func findKthLargest(nums []int, k int) int {
    small := make(minPriorityQueue, 0)
    heap.Init(&small)
    for _, num := range nums {
        heap.Push(&small, num)
        if small.Len() > k {
            heap.Pop(&small)
        }
    }
    return heap.Pop(&small).(int)
}

复杂度分析

令 n 为数组长度。

时间复杂度：$O(nlogn)$
空间复杂度：$O(n)$

chakochako commented 2 years ago

import heapq as h

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

        for num in nums:
            # 如果堆长度没到k，无脑塞
            if len(heap) < k:
                h.heappush(heap, num)
            else:
                # 如果长度到k了，且当前元素比堆顶要大，我们才加进去，当然要先把最小的pop出来再加！
                if num > heap[0]:
                    h.heappop(heap)
                    h.heappush(heap, num)
        return h.heappop(heap)

RocJeMaintiendrai commented 2 years ago

代码

Quick Select Solution
class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length == 0) return 0;
        int left = 0;
        int right = nums.length - 1;
        while(true) {
            int pos = partition(nums, left, right);
            if(pos + 1 == k) {
                return nums[pos];
            } else if(pos + 1 > k) {
                right = pos - 1;
            } else {
                left = pos + 1;
            }
        }
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int l = left + 1;
        int r = right;
        while(l <= r) {
            if(nums[l] < pivot && nums[r] > pivot) {
                swap(nums, l++, r--);
            }
            if(nums[l] >= pivot) l++;
            if(nums[r] <= pivot) r--;
        }
        swap(nums, left, r);
        return r;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

复杂度分析

时间复杂度

O(n)

空间复杂度

O(1)

代码

PQ Solution
class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length == 0) return 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int num : nums) {
            pq.offer(num);
            if(pq.size() > k) {
                pq.poll();
            }
        }
        return pq.poll();
    }
}

复杂度分析

时间复杂度

O(nlogk)

空间复杂度

O(n)

Moin-Jer commented 2 years ago

思路

堆排序

代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }

    public void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    public void maxHeapify(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, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

复杂度分析

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

Yufanzh commented 2 years ago

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

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

Complexity Analysis

Time complexity: O(nlogk)
Space complexity: O(k)

chang-you commented 2 years ago

/*
quick select

*/

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int left = 0; 
        int right = nums.length - 1;
        while (true) {
            int pos = partition(nums,left, right);
            if (pos + 1 == k) {
                return nums[pos];
            } else if (pos + 1 > k) {
                right = pos - 1;
            } else {
                left = pos + 1;
            }
        }

    }

    public int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int l = left + 1;
        int r = right;
        while (l <= r) {
            if (nums[l] < pivot && nums[r] > pivot) {
                swap(nums, l++, r--);
            }
            if (nums[l] >= pivot) l++;
            if(nums[r] <= pivot) r--;
        }
        swap(nums, left, r);
        return r;

    }
    public void swap (int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;

    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        return minHeap.poll();
    }
}

// S: O(k) (PriorityQueue的size是k
// O(nlgk) 局部排序
// Array.sort: O(nlgn)
// PriorityQueue: O(nlgk)

tongxw commented 2 years ago

思路

维护一个size = k的小顶堆，把数字放在里面，如果size > k，那么堆顶的数字出堆。遍历到最后，堆顶的数字就是第k大的。

代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num: nums) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }

        return heap.peek();
    }
}

TC: O(nlogk) SC: O(k)

biscuit279 commented 2 years ago

思路：直接排序或者用小顶堆

#直接排序法
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort(reverse=True)
        return(nums[k-1])

#堆
"""
维护一个大小为K的小顶堆，堆顶是最小元素，当堆的size > K 的时候，删除堆顶元素. 扫描一遍数组，最后堆顶就是第K大的元素。 直接返回。
"""
import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        size = len(nums)
        h = []
        for i in range(k):
            heapq.heappush(h, nums[i])
        for j in range(k,size):
            if nums[j] >h[0]:
                heapq.heapreplace(h, nums[j])
        return h[0]

时间复杂度O(nlogk) 空间复杂度度O(n)

Menglin-l commented 2 years ago

思路：

1. 遍历一遍数组，把k个最大元素存放在某一种数据结构里。

2. 快速在这k个元素里找最小值，想到小顶堆。如果能把这这些元素存储在size为k的小顶堆里，那么堆顶元素就是第k大元素。从而避免对所有元素排序，降低时间复杂度。

3. 如果数据量特别大，比如当n=1000000，k=999996时，需要维护的小顶堆就会非常大。此时，我们可以将问题转化为找到第n - k + 1小的元素，用一个大顶堆来维护。

代码部分(小顶堆实现)：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //corner case
        if (nums.length < k) return 0;

        //build a min-heap in a k size
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);

        for (int i = 0; i < k; i ++) {
            pq.offer(nums[i]);
        }

        for (int i = k; i < nums.length; i ++) {
            if (nums[i] > pq.peek()) {
                pq.poll();
                pq.offer(nums[i]);
            }
        }

        return pq.peek();
    }
}

复杂度：

Time: O(N * logK)

Space: O(K)

ai2095 commented 2 years ago

215. Kth Largest Element in an Array

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

Topics

-Heap

思路

Heap

代码 Python

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = nums[:k]
        heapq.heapify(heap)
        for e in nums[k:]:
            if e > heap[0]:
                heapq.heappop(heap)
                heapq.heappush(heap, e)
        return heap[0]

复杂度分析

时间复杂度： O(N*Log(K))
空间复杂度： O(K)

ghost commented 2 years ago

题目

Kth Largest Element in an Array

代码


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

        for i in range(k):
            heapq.heappush(hq, nums[i])

        for i in range(k, len(nums)):
            if nums[i] > hq[0]:
                heapq.heappop(hq)
                heapq.heappush(hq, nums[i])

        return hq[0]

复杂度

Space: O(k) Time: O(nlogk)

TimmmYang commented 2 years ago

思路

Heap

代码

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = nums[:k]
        heapq.heapify(heap)
        for num in nums[k:]:
            if num > heap[0]:
                heapq.heappop(heap)
                heapq.heappush(heap, num)
        return heap[0]

复杂度

时间：O(nlogk) 空间：O(k)

naomiwufzz commented 2 years ago

思路：堆

代码

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        # 维护一个长度为k的小顶堆，那么这个堆有k个数比它大，最后取堆顶即可
        # 先初始化一个大小为k的小顶堆，依次入堆
        for i in range(k):
            heapq.heappush(heap, nums[i])
        for i in range(k, len(nums)):
            # 弹出最小的元素被新的元素替代
            if nums[i] > heap[0]:
                heapq.heapreplace(heap, nums[i])
        return heap[0]

复杂度分析

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

septasset commented 2 years ago

class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: if not nums or k < 1 or k > len(nums): return -1

    return self.quick_select(nums, 0, len(nums) - 1, k)

def quick_select(self, nums, start, end, k):
    if start == end:
        return nums[start]

    i, j = start, end
    pivot = nums[(i + j) // 2]

    while i <= j:
        while i <= j and nums[i] > pivot:
            i += 1
        while i <= j and nums[j] < pivot:
            j -= 1

        if i <= j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

    # start, j, i, end        
    if k <= j - start + 1:
        return self.quick_select(nums, start, j, k)

    if k >= i + 1 - start:
        # i - start is the total number of elements before index i
        return self.quick_select(nums, i, end, (k - (i - start)))

    return nums[j + 1]

m-z-w commented 2 years ago

var findKthLargest = function(nums, k) {
    return quickSelect(nums, 0, nums.length - 1, nums.length - k)
}

const quickSelect = (nums, l, r, index) => {
    const pos = partition(nums, l, r)
    if (pos === index) {
        return nums[pos]
    } else {
        return pos > index ? quickSelect(nums, l, pos - 1, index) : quickSelect(nums, pos + 1, r, index)
    }
}

const partition = (nums, l, r) => {
    const pivot = nums[r]
    let index = l
    for (let i = l; i < r; i++) {
        if (nums[i] < pivot) {
        i !== index && swap(nums, i, index)
        index++
        }
    }
    swap(nums, index, r)
    return index
}

const swap = (nums, i, j) => {
    const temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}

时间：O(n) 空间：O(logn)

mixtureve commented 2 years ago

class Solution {
  int [] nums;

  public void swap(int a, int b) {
    int tmp = this.nums[a];
    this.nums[a] = this.nums[b];
    this.nums[b] = tmp;
  }

  public int partition(int left, int right, int pivot_index) {
    int pivot = this.nums[pivot_index];
    // 1. move pivot to end
    swap(pivot_index, right);
    int store_index = left;

    // 2. move all smaller elements to the left
    for (int i = left; i <= right; i++) {
      if (this.nums[i] < pivot) {
        swap(store_index, i);
        store_index++;
      }
    }

    // 3. move pivot to its final place
    swap(store_index, right);

    return store_index;
  }

  public int quickselect(int left, int right, int k_smallest) {
    /*
    Returns the k-th smallest element of list within left..right.
    */

    if (left == right) // If the list contains only one element,
      return this.nums[left];  // return that element

    // select a random pivot_index
    Random random_num = new Random();
    int pivot_index = left + random_num.nextInt(right - left); 

    pivot_index = partition(left, right, pivot_index);

    // the pivot is on (N - k)th smallest position
    if (k_smallest == pivot_index)
      return this.nums[k_smallest];
    // go left side
    else if (k_smallest < pivot_index)
      return quickselect(left, pivot_index - 1, k_smallest);
    // go right side
    return quickselect(pivot_index + 1, right, k_smallest);
  }

  public int findKthLargest(int[] nums, int k) {
    this.nums = nums;
    int size = nums.length;
    // kth largest is (N - k)th smallest
    return quickselect(0, size - 1, size - k);
  }
}

laurallalala commented 2 years ago

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        # 维护一个长度为k的小顶堆，那么这个堆有k个数比它大，最后取堆顶即可
        # 先初始化一个大小为k的小顶堆，依次入堆
        for i in range(k):
            heapq.heappush(heap, nums[i])
        for i in range(k, len(nums)):
            # 弹出最小的元素被新的元素替代
            if nums[i] > heap[0]:
                heapq.heapreplace(heap, nums[i])
        return heap[0]

15691894985 commented 2 years ago

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

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

小顶堆

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        if not nums or k<1 or k>len(nums):
            return -1
        heap = []
        for i in range(k):
            heapq.heappush(heap,nums[i])
        for i in range(k,len(nums)):
            if nums[i]>heap[0]:
                heapq.heapreplace(heap,nums[i])
        return heap[0]

复杂度分析：

时间复杂度：O(nlogn) 建堆的时间代价是 O(n)，删除的总代价是 O(k \log n)

空间复杂度：O（k）

mokrs commented 2 years ago

int findKthLargest(vector<int>& nums, int k) {    
    priority_queue<int> q;
    for (auto &num : nums){
        q.push(num);
    }

    for (int i = 0; i < k - 1; ++i){
        q.pop();
    }

    return q.top();
}

RonghuanYou commented 2 years ago

from heapq import *

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        minHeap = []
        for i in range(k):
            heappush(minHeap, nums[i])

        for i in range(k, len(nums)):
            if nums[i] > minHeap[0]:
                heappushpop(minHeap, nums[i])     
        return minHeap[0]

ysy0707 commented 2 years ago

思路：堆排序

class Solution {
    //利用优先队列实现最小堆：遍历原数组的值，添加到堆中（想象成堆的容量为k）
    //如果堆中元素的个数小于等于k的时候，我们就往堆中添加，
    //添加之后如果堆中元素个数大于k的时候，我们就把最顶端的元素给移除掉，
    //这样留到最后，最小堆堆顶的值正好就是第k大个数
    public int findKthLargest(int[] nums, int k) {
        //java优先队列默认就是优先取到小的元素，即小顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int val: nums){
            queue.add(val);
            if(queue.size() > k){
                queue.poll();
            }
        }
        return queue.peek();
    }
}

时间复杂度：O(NlogN) 空间复杂度：O(N)

leetcode-pp / 91alg-5-daily-check

【Day 85 】2021-12-03 - 215. 数组中的第 K 个最大元素 #104

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

入选理由

题目地址

前置知识

题目描述

思路

方法: 堆排序

代码

实现语言: C++

复杂度分析

Idea:

Code:

Complexity:

思路

关键点

代码

idea

code

complexity

Note

Solution

思路1 - PQ/min heap

Java Code

时间&空间

思路2 - 快速排序partition

Java Code

时间&空间

思路

代码

思路

代码(C++)

复杂度分析

代码

复杂度

Golang代码215

思路

代码

复杂度

代码

复杂度

JAVA版本

思路：

解题思路

代码

思路

代码块

thoughts

code

Complexity

Problem

Note

Solution

Complexity

思路

Python代码

题目

思路

python3

复杂度分析

相关题目

思路

复杂度

思路

代码

代码

复杂度分析

时间复杂度

空间复杂度

代码

复杂度分析

时间复杂度

空间复杂度

思路

代码

复杂度分析

Complexity Analysis

思路

代码