Open azl397985856 opened 2 years ago
yetfan
commented
2 years ago 思路 堆排序
代码
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
p = []
for n in nums:
heapq.heappush(p, -n)
for _ in range(k - 1):
heapq.heappop(p)
return -p[0]
复杂度 时间 O(n) 空间 O(n)
zjsuper
commented
2 years ago import heapq
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
lens = len(nums)
h = []
for i in range(k):
heapq.heappush(h,nums[i])
for i in range(k,lens):
if nums[i] > h[0]:
heapq.heapreplace(h,nums[i])
return h[0]
youzhaing
commented
2 years ago 大根堆
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
h = []
res = 0
for num in nums:
heapq.heappush(h, -num)
for _ in range(k):
res = -heapq.heappop(h)
return res
cszys888
commented
2 years ago class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
n = len(nums)
heapq.heapify(nums)
k = n - k + 1
for i in range(k - 1):
heapq.heappop(nums)
return heapq.heappop(nums)time complexity: O(nlogn) space complexity: O(logn)
herbertpan
commented
2 years ago kth: Queue, QuickPartition
class Solution {
public int findKthLargest(int[] nums, int k) {
int start = 0;
int end = nums.length - 1;
int partitionIndex = findPartitionIndex(nums, start, end);
while (partitionIndex != nums.length - k) {
if (partitionIndex < nums.length - k) {
start = partitionIndex + 1;
} else {
end = partitionIndex - 1;
}
partitionIndex = findPartitionIndex(nums, start, end);
}
return nums[partitionIndex];
}
private int findPartitionIndex(int[] nums, int start, int end) {
int pivot = nums[start];
int index = start + 1;
for (int pointer = start + 1; pointer <= end; pointer++) {
if (nums[pointer] < pivot) {
swap(nums, index, pointer);
index++;
}
}
swap(nums, index - 1, start);
return index - 1;
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
yan0327
commented
2 years ago type hp []int
func (h hp) Len() int{return len(h)}
func (h hp) Less(i,j int) bool{return h[i]<h[j]}
func (h hp) Swap(i,j int){h[i],h[j] = h[j],h[i]}
func (h *hp) Push(x interface{}){ *h = append(*h,x.(int))}
func(h *hp) Pop() interface{}{
x := *h
out := x[len(x)-1]
*h = x[:len(x)-1]
return out
}
func findKthLargest(nums []int, k int) int {
h := &hp{}
heap.Init(h)
for i := range nums{
heap.Push(h,nums[i])
if h.Len() > k{
heap.Pop(h)
}
}
return heap.Pop(h).(int)
}func findKthLargest(nums []int, k int) int {
quickSort(nums,0,len(nums)-1,k)
return nums[k-1]
}
func quickSort(nums []int,left int,right int,k int){
if left >= right{
return
}
mid := left + (right-left)>>1
nums[mid],nums[right] = nums[right],nums[mid]
i := left-1
for j:=left;j<right;j++{
if nums[j] > nums[right]{
i++
nums[i],nums[j] = nums[j],nums[i]
}
}
i++
nums[i],nums[right] = nums[right],nums[i]
now := i-left+1
if now == k{
return
}else if now < k{
quickSort(nums,i+1,right,k-now)
}else{
quickSort(nums,left,i-1,k)
}
}
wdwxw
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;
}}
Tesla-1i
commented
2 years ago class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
h = []
res = 0
for num in nums:
heapq.heappush(h, -num)
for _ in range(k):
res = -heapq.heappop(h)
return res
Aobasyp
commented
2 years ago 思路 小顶堆 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();
}}
时间复杂度：O(n * logk) 空间复杂度：O(k)
moirobinzhang
commented
2 years ago Code:
public int FindKthLargest(int[] nums, int k) {
Dictionary<int, int> numDict = new Dictionary<int, int>();
foreach(int num in nums)
{
if (!numDict.ContainsKey(num))
numDict.Add(num, 0);
numDict[num]++;
}
foreach(var item in numDict.OrderByDescending(n => n.Key))
{
k -= item.Value;
if ( k <= 0)
return item.Key;
}
return 0;
}
ZacheryCao
commented
2 years ago Heap
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue <int> pq;
for(auto i:nums){
if(pq.size()<k){
pq.push(-i);
}else{
if(-i<pq.top()){
pq.pop();
pq.push(-i);
}
}
}
return -pq.top();
}
};Time: O(N logk) Space; O(N)
zhangzz2015
commented
2 years ago C++ Code:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// heap or quick select.
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(pq.size()==k)
{
if(pq.top()<nums[i])
{
pq.pop();
pq.push(nums[i]);
}
}
}
return pq.top();
}
};
复杂度分析
xjhcassy
commented
2 years ago class KthLargestElementSort {
public int findKthlargest2(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
Size-of
commented
2 years ago class KthLargestElementSort {
public int findKthlargest2(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}}
xinhaoyi
commented
2 years ago class Solution { //这题用快排做出来了，别的操作也没学了 public int findKthLargest(int[] nums, int k) { return getTopK(nums, k); }
// 分治
public int partition(int[] nums, int low, int high) {
int pivot = nums[low];
while (low < high) {
while (low < high && nums[high] <= pivot) {
high--;
}
nums[low] = nums[high];
while (low < high && nums[low] >= pivot) {
low++;
}
nums[high] = nums[low];
}
nums[low] = pivot;
return low;
}
// 获得 Kth 的数
public int getTopK(int[] nums, int k) {
int low = 0;
int high = nums.length - 1;
// 不断调整分治的位置，直到 position = k - 1
while (true) {
int index = partition(nums, low, high);
if (index == k - 1) {
return nums[index];
}
else if (index < k - 1) {
low = index + 1;
}
else {
high = index - 1;
}
}
}}
Brent-Liu
commented
2 years ago class KthLargestElementSort {
public int findKthlargest2(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}}
dahaiyidi
commented
2 years ago ++
给定整数数组 nums 和整数 k，请返回数组中第 **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
输出: 4class Solution {
public:
int partition(vector<int>& nums, int left, int right){
int mid = rand() % (right - left + 1) + left;
swap(nums[mid], nums[right]);
int pivot = nums[right];
int i = left, j = left;
// 将<pivot 的值放到左边，> pivot 的值放到右边
// i是将要放置< pivot的值的最新位置 (i 为第一个>= pivot的位置)
while(j < right){
if(nums[j] < pivot){
// nums[j] < pivort，将nums[j] 与 nums[i] 交换
swap(nums[i], nums[j]);
i++;
j++;
}
else{
// nums[j] >= pivot， 右移j
j++;
}
}
swap(nums[i], nums[right]);
return i; //返回pivot的所在位置
}
void func(vector<int>& nums, int left, int right, int k){
int mid = partition(nums, left, right);
if(mid == k){
return;
}
else if(mid < k){
func(nums, mid + 1, right, k);
}
else if(mid > k){
func(nums, left, mid - 1, k);
}
}
int findKthLargest(vector<int>& nums, int k) {
// 第k大就是，第nums.size() - k + 1小, 也就是索引为nums.size() - k
func(nums, 0, nums.size() - 1, nums.size() - k);
return nums[nums.size() - k];
}
};
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;
}
}
Serena9
commented
2 years ago 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]
LannyX
commented
2 years ago 直接排序
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
haixiaolu
commented
2 years ago class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
maxHeap = []
for i in nums:
heapq.heappush(maxHeap, -i)
for _ in range(k - 1):
heapq.heappop(maxHeap)
return -maxHeap[0]
1149004121
commented
2 years ago 思路
最小堆
代码
var findKthLargest = function(nums, k) {
let heap = new MinPriorityQueue();
for(let i = 0; i < nums.length; i++){
heap.enqueue("X", nums[i]);
if(heap.size() > k) heap.dequeue();
};
return heap.dequeue()["priority"];
};复杂度分析
Myleswork
commented
2 years ago 这没什么好说的
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.rbegin(),nums.rend());
return nums[k-1];
}
};复杂度分析
时间复杂度：O(nlgn)
空间复杂度：O(1)
维护一个大小为k的小顶堆，最后堆顶即为第k个最大的元素
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//大小为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();
}
};复杂度分析
时间复杂度：O(n)
空间复杂度：O(k)
xuhzyy
commented
2 years ago class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
q = []
for num in nums:
heapq.heappush(q, num)
if len(q) > k:
heapq.heappop(q)
return q[0]
alongchong
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;
}
}
ZJP1483469269
commented
2 years ago class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
p = []
for num in nums:
heappush(p , -num)
ans = 0
while k:
k -= 1
ans = heappop(p)
print(k , -ans)
return -ans
rockydale
commented
2 years ago var findKthLargest = function(nums, k) {
//拿到k个元素原地建小顶堆 堆顶元素就是第k个最大的
let heap = [,] , i = 0
while(i<k){
heap.push(nums[i++])
}
buildHeap(heap , k)
for(let i = k ; i < nums.length ; i++){
if(heap[1] < nums[i]){
heap[1] = nums[i]
heapify(heap , k , 1)
}
}
return heap[1]
};
//原地建堆 从后往前 自上而下建立小顶堆
let buildHeap = (arr , k) =>{
if(k ===1) return
//从最后一个非叶子节点开始 自上而下式堆化
for(let i = Math.floor(k / 2) ; i>=1 ; i--){
heapify(arr , k , i)
}
}
let heapify = (arr , k , i) =>{
while(1){
let minIndex = i
if(2 * i <= k && arr[2*i] < arr[i]){
minIndex = 2*i
}
if(2 * i + 1 <=k && arr[2*i +1] < arr[minIndex]){
minIndex = 2 * i +1
}
if(minIndex !== i){
swap(arr , i , minIndex)
i = minIndex
}else{
break
}
}
}
let swap = (arr , i , j) =>{
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
Arya-03
commented
2 years ago class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
quicksort(0,len(nums)-1,nums)
print(nums)
return(nums[k-1])
def quicksort(left,right,target):
#left=1
#right=len(nums)
if (left>right):
return
temp=target[left]
i=left
j=right
while(i!=j):
while(target[j]<=temp and i<j):
j-=1
while(target[i]>=temp and i<j):
i+=1
if(i<j):
t=target[i]
target[i]=target[j]
target[j]=t
target[left]=target[i]
target[i]=temp
quicksort(left,i-1,target)
quicksort(i+1,right,target)
return target
testeducative
commented
2 years ago
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, less<int>> pq;
for(auto num: nums){
pq.push(num);
}
int res = 0;
for(int i = 0; i < k; i++){
if(i == k-1){
res = pq.top();
}
pq.pop();
}
return res;
}
};
biscuit279
commented
2 years ago 先用前k个元素生成一个最小堆，再不断用剩下元素的替换最小值，最后堆顶元素就是第k大的数
import heapq
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
n = len(nums)
h = []
#生成一个大小为k的最小堆
for i in range(k):
heapq.heappush(h, nums[i])
for i in range(k,n):
if nums[i] > h[0]: # 比最小的数大
heapq.heapreplace(h,nums[i]) #删除最小元素，添加新元素
return h[0]时间复杂度：O（nlogk） 空间复杂度：O（k）
callmeerika
commented
2 years ago 堆排序
var swap = (nums, i, j) => {
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
};
var buildMaxHeap = (nums, size) => {
for(let i = Math.floor(size/2) - 1; i >= 0; i--){
maxHeapify(nums, i, size);
}
};
var maxHeapify = (nums, i, size) => {
let l = i*2 + 1;
let r = i*2 + 2;
let largest = i;
if(l < size && nums[l] > nums[largest]){
largest = l;
}
if(r < size && nums[r] > nums[largest]){
largest = r;
}
if(largest !== i){
swap(nums, i, largest);
maxHeapify(nums, largest, size);
}
}
var findKthLargest = function(nums, k) {
let size = nums.length;
buildMaxHeap(nums, size);
for(let i = nums.length - 1; i >= nums.length - k + 1; i--){
swap(nums, 0, i);
--size;
maxHeapify(nums, 0, size);
}
return nums[0];
};时间复杂度：O(nlogn)
空间复杂度：O(logn)
guangsizhongbin
commented
2 years ago func findKthLargest(nums []int, k int) int { nums = heapSort(nums) return nums[k-1] }
func heapSort(nums []int) []int { lens := len(nums) // 先建立一个堆 buildHeap(nums,lens) // 上面构建堆后,其实已经满足了基本的 最大堆或者最小堆 // 此时根节点肯定是最大值或者最小值了 // 从数组最后挨个往前遍历 for i:=lens-1;i>=0;i-- { // 构成堆后的数组的第一个值和最后一个值进行替换 // 然后把 数组 i 个值之后的数之外的数 继续构建堆 // 循环往复 swap(nums,0,i) lens -= 1 heap(nums,0,lens) } return nums }
// 构建一个堆 func buildHeap(nums []int,lens int) { // 一般数组长度的一半 很可能就不是叶子节点了,但可以确定的是 数组长度一半后面的肯定都是叶子节点 // 叶子节点是最底下的节点了,所以不需要往下置换了,所以从 长度/2开始算 for i := lens/2;i>=0;i-- { heap(nums,i,lens) } }
func heap(nums []int,i,lens int) { // 每个父节点的左节点 是当前数组下标i的 2i + 1 // 每个父节点的右节点 是当前数组下标i的 2i + 2 left := 2i + 1 right := 2i + 2
// 咱们做最小堆,也就是小的数组排在后面
// 假设当前的 父节点是最小
min := i
// 当 父节点的左子节点 小于 数组总长度 且 左子节点的值小于父节点的时候,所以这个小堆里 左子节点是最小的(暂时不替换)
// 为什么要 父节点的左子节点 小于 数组总长度, 因为如果父节点的左子节点比 数组总长度还长,那说明 超出了数组范围了..说明该父节点其实没有左子节点
if left < lens && nums[left] < nums[min] {
min = left
}
// 右子节点跟上面左子节点一个道理
if right < lens && nums[right] < nums[min] {
min = right
}
// 如果通过上面与左右子节点相比,最小值已经不是当初的父节点了
// 那么把最小的节点与父节点进行变换,变换后可能会影响该父节点的子节点的子节点,所以还得往下继续对比比换一下
if min != i {
swap(nums,min,i)
heap(nums,min,lens)
}}
func swap(arr []int,m,n int) []int { arr[m],arr[n] = arr[n],arr[m] return arr }
hdyhdy
commented
2 years ago type hp []int
func (h hp) Len() int{return len(h)}
func (h hp) Less(i,j int) bool{return h[i]<h[j]}
func (h hp) Swap(i,j int){h[i],h[j] = h[j],h[i]}
func (h *hp) Push(x interface{}){ *h = append(*h,x.(int))}
func(h *hp) Pop() interface{}{
x := *h
out := x[len(x)-1]
*h = x[:len(x)-1]
return out
}
func findKthLargest(nums []int, k int) int {
h := &hp{}
heap.Init(h)
for i := range nums{
heap.Push(h,nums[i])
if h.Len() > k{
heap.Pop(h)
}
}
return heap.Pop(h).(int)
}
fornobugworld
commented
2 years ago class Solution: import heapq def findKthLargest(self, nums: List[int], k: int) -> int: heap = [] for i in nums: if len(heap) <= k: heapq.heappush(heap,i) if len(heap) > k: heapq.heappop(heap) return heapq.heappop(heap)
charlestang
commented
2 years ago 最小堆。
构造一个 大小为 k 的最小堆，把数字推入堆后，弹出堆顶数字，使堆整体的大小保持 k。 最后，堆顶元素就是第 k 大的元素。
时间复杂度 O(n log k) 空间复杂度 O(k)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
cnt = 0
q = []
for n in nums:
if cnt < k:
heapq.heappush(q, n)
cnt += 1
else:
heapq.heappushpop(q, n)
return q[0]
Hacker90
commented
2 years ago var swap = (nums, i, j) => { let temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }; var buildMaxHeap = (nums, size) => { for(let i = Math.floor(size/2) - 1; i >= 0; i--){ maxHeapify(nums, i, size); } }; var maxHeapify = (nums, i, size) => { let l = i2 + 1; let r = i2 + 2; let largest = i; if(l < size && nums[l] > nums[largest]){ largest = l; } if(r < size && nums[r] > nums[largest]){ largest = r; } if(largest !== i){ swap(nums, i, largest); maxHeapify(nums, largest, size); } } var findKthLargest = function(nums, k) { let size = nums.length; buildMaxHeap(nums, size); for(let i = nums.length - 1; i >= nums.length - k + 1; i--){ swap(nums, 0, i); --size; maxHeapify(nums, 0, size); } return nums[0]; };
Riuusee
commented
2 years ago 堆
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();
}
}
复杂度分析
hx-code
commented
2 years ago var swap = (nums, i, j) => { let temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }; var buildMaxHeap = (nums, size) => { for(let i = Math.floor(size/2) - 1; i >= 0; i--){ maxHeapify(nums, i, size); } }; var maxHeapify = (nums, i, size) => { let l = i2 + 1; let r = i2 + 2; let largest = i; if(l < size && nums[l] > nums[largest]){ largest = l; } if(r < size && nums[r] > nums[largest]){ largest = r; } if(largest !== i){ swap(nums, i, largest); maxHeapify(nums, largest, size); } } var findKthLargest = function(nums, k) { let size = nums.length; buildMaxHeap(nums, size); for(let i = nums.length - 1; i >= nums.length - k + 1; i--){ swap(nums, 0, i); --size; maxHeapify(nums, 0, size); } return nums[0]; };
GaoMinghao
commented
2 years ago 堆/快速排序
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for(int num:nums)
heap.add(num);
int ans = 0;
for(int i = 0; i < nums.length-k+1; i++) {
ans = heap.poll();
}
return ans;
}
}O(nlogn)
z1ggy-o
commented
2 years ago 背一个 quick_select
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return quick_select(nums, 0, nums.size() - 1, k);
}
int quick_select(vector<int>& nums, int start, int end, int k)
{
if (start == end) return nums[start];
int left = start;
int right = end;
int pivot = nums[left + (right - left) / 2];
while (left <= right) {
while (left <= right && nums[left] > pivot) left++;
while (left <= right && nums[right] < pivot) right--;
if (left <= right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
if (start + k - 1 <= right)
return quick_select(nums, start, right, k);
if (start + k - 1 >= left)
return quick_select(nums, left, end, start + k - left);
return nums[right + 1];
}
};复杂度分析
codingPitaya
commented
2 years ago class Heap {
constructor(arr, compare) {
this.compare = compare;
this.arr = arr;
for (let i = ((this.arr.length >> 1) - 1); i >= 0; i--) {
this.heapify(i);
}
}
push(item) {
this.arr.push(item);
let index = this.arr.length - 1;
let father = Math.floor((index - 1) / 2);
while ((father >= 0) && this.compare(this.arr[index], this.arr[father])) {
this.swap(index, father);
index = father;
father = Math.floor((index - 1) / 2);
}
}
pop() {
this.swap(0, this.arr.length - 1);
let ret = this.arr.pop();
this.heapify(0);
return ret;
}
heapify(index) {
let tmp = index;
let l = tmp * 2 + 1;
let r = tmp * 2 + 2;
if ( l < this.arr.length && this.compare(this.arr[l], this.arr[tmp]) ) {
tmp = l;
}
if ( r < this.arr.length && this.compare(this.arr[r], this.arr[tmp]) ) {
tmp = r;
}
if (tmp !== index) {
this.swap(tmp, index);
this.heapify(tmp);
}
}
swap(l, r) {
[this.arr[l], this.arr[r]] = [this.arr[r], this.arr[l]];
}
}
var findKthLargest = function(nums, k) {
let pq = new Heap(nums, (lower, higher) => lower > higher);
while (k-- > 1) {
pq.pop();
}
return pq.arr[0];
};
HWFrankFung
commented
2 years ago let findKthLargest = function (nums, k) {
let len = nums.length;
let l = 0;
let r = nums.length - 1;
while (l <= r) {
let p = partition(nums, l, r);
if (p === k - 1) return nums[p];
else if (p > k - 1) {
r = p - 1;
}
else l = p + 1;
}
}
function partition(nums, begin, end) {
let l = begin;
let r = end;
let temp = nums[begin];
while (l < r) {
while (l < r && nums[r] <= temp) r--;
while (l < r && nums[l] >= temp) l++;
if (l < r) {
let t = nums[r];
nums[r] = nums[l];
nums[l] = t;
}
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];
}
}
zzzpppy
commented
2 years ago class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
Arrays.sort(nums);
return nums[len - k];
}
}
taojin1992
commented
2 years ago /*
time:
best/avg: O(n), divide in half, drop one half
worst: O(n^2), poor pivot
space: O(1)
*/
class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, k);
}
// k - largest
// 5 4 3 2 1
// k = 2, len = 5, targetindex = len - k = 3
private int quickSelect(int[] nums, int start, int end, int k) {
while (true) {
if (start > end) {
throw new RuntimeException("Invalid");
}
int pivotIndex = start;
int left = start + 1, right = end;
while (left <= right) {
if (nums[left] > nums[pivotIndex] && nums[right] <= nums[pivotIndex]) {
swap(nums, left, right);
}
if (nums[left] <= nums[pivotIndex]) {
left++;
}
if (nums[right] > nums[pivotIndex]) {
right--;
}
}
swap(nums, pivotIndex, right);
if (right == nums.length - k) {// nums.length - right == k
return nums[right];
} else if (right < nums.length - k) { // nums.length - right > k, right too small
start = right + 1;
} else {
end = right - 1;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
for123s
commented
2 years ago class Solution {
public:
int quicksort(vector<int>& nums, int l, int r, int idx)
{
int res = randpartition(nums, l, r);
if(res == idx)
return res;
else if(res < idx)
return quicksort(nums,res+1,r,idx);
else
return quicksort(nums,l,res-1,idx);
}
int randpartition(vector<int>& nums, int l, int r)
{
int i = rand()%(r-l+1)+l;
swap(nums[i], nums[r]);
return partition(nums, l, r);
}
int partition(vector<int>& nums, int l, int r)
{
int i = l;
for(int j=l;j<r;++j)
if(nums[j]<nums[r])
{
swap(nums[i],nums[j]);
++i;
}
swap(nums[i],nums[r]);
return i;
}
int findKthLargest(vector<int>& nums, int k) {
srand(time(NULL));
return nums[quicksort(nums,0,nums.size()-1,nums.size()-k)];
}
};
falconruo
commented
2 years ago 思路:
堆排序
复杂度分析:
代码(C++):
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> qt;
for (int i = 0; i < nums.size(); ++i) {
if (qt.empty() || qt.size() < k)
qt.push(nums[i]);
else if (qt.top() < nums[i]) {
qt.pop();
qt.push(nums[i]);
}
}
return qt.top();
}
};其实单纯地排序也可以做，无非就是要承担频繁插入的代价
所以采用大顶堆，以lgn的时间复杂度来完成插入操作
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int, vector<int>, less<int>> sq;
for (int s : stones) {
sq.push(s);
}
while (sq.size() >= 2) {
int a = sq.top();
sq.pop();
int b = sq.top();
sq.pop();
if (a != b) sq.push(a-b);
}
return sq.size() > 0 ? sq.top() : 0;
}
};复杂度分析
时间复杂度：O(nlgn) 遍历*插入
空间复杂度：O(n)
Alfie100
commented
2 years ago class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
hp = nums[:k]
heapq.heapify(hp)
for num in nums[k:]:
if num > hp[0]:
# heapq.heappushpop(hp, num)
heapq.heapreplace(hp, num)
return hp[0]
tian-pengfei
commented
2 years ago class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int,vector<int>,greater<>> q;
for (auto const num:nums){
if(q.size()<k){
q.push(num);
continue;
}
int min = q.top();
if(min < num){
q.pop();
q.push(num);
}
}
return q.top();
}
};
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 ≤ 数组的长度。