【重点!!!】【堆】【快排】215.数组中的第K个最大元素

文章介绍了两种在Java中查找数组中第K个最大元素的方法:使用小根堆实现的优先队列法和基于快速排序的划分与递归法。通过实例代码展示了这两种算法的思路和实现过程。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

题目
在这里插入图片描述

Python

快排法

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return self.quickSort(nums, k)
    
    def quickSort(self, nums, count):
        bigger = list()
        same = list()
        smaller = list()
        label = random.choice(nums) # 随机选择用法
        for item in nums:
            if item > label:
                bigger.append(item)
            elif item < label:
                smaller.append(item)
            else:
                same.append(item)
        
        if count <= len(bigger): # 注意: 这里一定包含等号
            return self.quickSort(bigger, count)
        elif count > len(bigger) + len(same): # 注意: 这里一定不包含等号
            return self.quickSort(smaller, count - len(bigger) - len(same))
        else:
            return label

小根堆

最大的K个元素 => 小根堆(类似上窄下宽的梯形),最大的第k个就是堆顶元素
最小的K个元素 => 大根堆(类似倒三角形),最小的第k个就是堆顶元素
python中小根堆用法:https://blog.csdn.net/weixin_40134371/article/details/139996858

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

        return min_heap[0]

偷鸡摸狗法

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # nums.sort(reverse=True) # 这种排序也可
        return sorted(nums)[len(nums) - k]

Java

法1:小根堆

最大的K个元素 => 小根堆(类似上窄下宽的梯形)
最小的K个元素 => 大根堆(类似倒三角形)
必须掌握!!!

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int i = 0; i < k; ++i) {
            q.offer(nums[i]);
        }

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

        return q.peek();
    }
}

法2:基于快排

class Solution {
    public int findKthLargest(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        for (int i : nums) {
            list.add(i);
        }

        return quickSelect(list, k);
    }

    public int quickSelect(List<Integer> list, int k) {
        int n = list.size();
        Random rand = new Random();
        int rInx = rand.nextInt(n); // 生成0 ~ n-1之间的整数
        List<Integer> big = new ArrayList<>();
        List<Integer> same = new ArrayList<>();
        List<Integer> small = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (list.get(i) > list.get(rInx)) {
                big.add(list.get(i));
            } else if (list.get(i) == list.get(rInx)) {
                same.add(list.get(i));
            } else {
                small.add(list.get(i));
            }
        }

        if (big.size() >= k) {
            return quickSelect(big, k);
        } else if (k > (big.size() + same.size())) {
            return quickSelect(small, k - (big.size() + same.size()));
        } else {
            return list.get(rInx);
        }
    }
}
这个错误是由于无法连接到本地主机的10248端口导致的。这个端口通常是kubelet进程监听的端口,用于健康检查。出现这个错误可能是由于kubelet进程没有正确启动或者配置错误导致的。 解决这个问题的方法是检查kubelet进程的状态和配置。你可以按照以下步骤进行操作: 1. 检查kubelet进程是否正在运行。你可以使用以下命令检查kubelet进程的状态: ```shell systemctl status kubelet ``` 如果kubelet进程没有运行,你可以使用以下命令启动它: ```shell systemctl start kubelet ``` 2. 检查kubelet的配置文件。你可以使用以下命令查看kubelet的配置文件路径: ```shell kubelet --kubeconfig /etc/kubernetes/kubelet.conf --config /var/lib/kubelet/config.yaml --bootstrap-kubeconfig /etc/kubernetes/bootstrap-kubelet.conf config view ``` 确保配置文件中的端口号和地址正确,并且与你的环境相匹配。 3. 检查网络连接。你可以使用以下命令检查是否可以连接到localhost10248端口: ```shell curl -sSL http://localhost:10248/healthz ``` 如果无法连接,请确保端口没有被防火墙或其他网络配置阻止。 4. 检查docker的配置。有时候,kubelet进程依赖于docker进程。你可以按照以下步骤检查docker的配置: - 创建/etc/docker目录: ```shell sudo mkdir /etc/docker ``` - 编辑/etc/docker/daemon.json文件,并添加以下内容: ```json { "exec-opts": ["native.cgroupdriver=systemd"], "log-driver": "json-file", "log-opts": { "max-size": "100m" }, "storage-driver": "overlay2", "storage-opts": [ "overlay2.override_kernel_check=true" ], "registry-mirrors": ["https://tdhp06eh.mirror.aliyuncs.com"] } ``` - 重启docker进程: ```shell systemctl restart docker ``` 请注意,以上步骤是一种常见的解决方法,但具体解决方法可能因环境而异。如果以上步骤无法解决问题,请提供更多的错误信息和环境配置,以便我们能够更好地帮助你。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值