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

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路:最开始排序算法,弄完之后直接按照要求选择,可惜题目对时间复杂度有要求,只能上快排,但是快排并不是直接满足,还需要在基础上优化。快排采取分治的思想,正常递归需要子串都进行排序,最后合并,但是找出结果有个便利的点就是可以判断在那个串里面,选择性的进行快排来加速。

#include <iostream>
#include <vector>

using namespace std;
//选择排序
// class Solution {
// public:
//     int findKthLargest(vector<int>& nums, int k) {
//         for (int i = 0; i < nums.size(); i++){
//             int min_index = i; // 记录最小值的索引
//             for (int j = i; j < nums.size(); j++){
//                 if (nums[j] < nums[min_index]){
//                     min_index = j;
//                 }
//             }
//             swap(nums[min_index], nums[i]);
//         }
//         return nums[nums.size() - k];
//     }
// };


class Solution {
public:
    int aparthSort(vector<int>& nums, int left, int right){
        int i = left, j = right;
        int pivot = nums[left];
        while (i < j) {
            while (i < j) {
                if (nums[j] < pivot) {
                    nums[i] = nums[j];
                    i++;
                    break;
                }
                else 
                    j--;
            }

            while (i < j) {
                if (nums[i] > pivot) {
                    nums[j] = nums[i];
                    j--;
                    break;
                }
                else
                    i++;
            }
        }
        nums[i] = pivot;
        return i;
    }

    int sort (vector<int>& nums, int left, int right, int k) {
        int mid;
        if (left < right){
            mid = aparthSort(nums, left, right);
            if (mid == nums.size() - k) return nums[mid];
            else if (mid > nums.size() - k) return sort(nums, left, mid - 1, k);
            else return sort(nums, mid + 1, right, k);
        }
        else    return nums[nums.size() - k];
    }

    int findKthLargest(vector<int>& nums, int k) {
        int res =  sort(nums, 0, nums.size() - 1, k);
        return res;
    }
};



int main(){
    Solution s;
    vector<int> nums = {3,2,1,5,6,4};
    // vector<int> nums = {1};
    int k = 4;
    cout << s.findKthLargest(nums, k) << endl;

    for (int i = 0; i < nums.size(); i++){
        cout << nums[i] << " ";
    }
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/415746.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

LeetCode 2125.银行中的激光束数量

银行内部的防盗安全装置已经激活。给你一个下标从 0 开始的二进制字符串数组 bank &#xff0c;表示银行的平面图&#xff0c;这是一个大小为 m x n 的二维矩阵。 bank[i] 表示第 i 行的设备分布&#xff0c;由若干 ‘0’ 和若干 ‘1’ 组成。‘0’ 表示单元格是空的&#xff0…

打卡今天内存管理

首先我们的体系结构是这样的&#xff0c;根据小林coding 来写的笔记 寄存器&#xff0c;速度非常快&#xff0c; 32位的可以存4个字节&#xff0c;64位的可以存8个字节 多少位只是在32位以上 地址空间 分为两种地址空间 &#xff1a; 物理&#xff0c;逻辑 地址空间 地址空间…

推荐5个python可视化库

你是否曾为数据可视化而烦恼&#xff1f; 在浩瀚的数据海洋中&#xff0c;如何将复杂的数据以直观、易懂的方式展现出来&#xff0c;成为了每个数据分析师和开发者必须面对的挑战。 幸运的是&#xff0c;我们有众多强大的可视化工具可以选择。 推荐5个Python可视化库&#x…

rtthread stm32h743的使用(四)pin设备使用

我们要在rtthread studio 开发环境中建立stm32h743xih6芯片的工程。我们使用一块stm32h743及fpga的核心板完成相关实验&#xff0c;核心板如图&#xff1a; 1.首先建立rtthread工程 2.添加相关程序如下&#xff0c;我们在上一节的代码中添加相关代码&#xff1a; #include &…

分享一点PDF中获取表格的探索过程

版面分析&#xff1a;如何得到标题、如何的得到段落&#xff08;正确的段落&#xff09;、如何得到表格、如何得到图片&#xff0c;图和得到图片上的文字&#xff1f; 还有细节问题&#xff1a;双栏和多栏的问题、公式问题 扫描件&#xff1a;扫描件本质上是图片&#xff0c;如…

oracle with check option 学习

with check option保证了通过视图进行的修改&#xff0c;必须也能通过该视图看到修改后的结果&#xff1b; 你插入&#xff0c;那么插入这条记录在刷新视图后必须可以看到&#xff1b; 如果修改&#xff0c;修改完的结果也必须能通过该视图看到&#xff1b; scott登录了以后创…

React中使用useActive

1.引入 import { useActivate } from "react-activation";2.React Activation 在React中使用react-activation,其实就是类似于Vue中的keep-alive&#xff0c;实现数据的缓存&#xff1b; 源码&#xff1a; import { ReactNode, ReactNodeArray, Context, Component…

YOLOv8改进,添加GSConv+Slim Neck,有效提升目标检测效果,代码改进(超详细)

目录 摘要 主要想法 GSConv GSConv代码实现 slim-neck slim-neck代码实现 yaml文件 完整代码分享 总结 摘要 目标检测是计算机视觉中重要的下游任务。对于车载边缘计算平台来说&#xff0c;巨大的模型很难达到实时检测的要求。而且&#xff0c;由大量深度可分离卷积层构…

2024-02-28(Kafka,Oozie,Flink)

1.Kafka的数据存储形式 一个主题由多个分区组成 一个分区由多个segment段组成 一个segment段由多个文件组成&#xff08;log&#xff0c;index&#xff08;稀疏索引&#xff09;&#xff0c;timeindex&#xff08;根据时间做的索引&#xff09;&#xff09; 2.读数据的流程 …

Laravel - API 项目适用的图片验证码

1. 安装 gregwar/captcha 图片验证码接口的流程是&#xff1a; 生成图片验证码 生成随机的 key&#xff0c;将验证码文本存入缓存。 返回随机的 key&#xff0c;以及验证码图片 # 不限于 laravel 普通 php 项目也可以使用额 $ composer require gregwar/captcha2. 开发接口 …

51单片机(6)-----直流电机的介绍与使用(通过独立按键控制电机的运行)

前言&#xff1a;感谢您的关注哦&#xff0c;我会持续更新编程相关知识&#xff0c;愿您在这里有所收获。如果有任何问题&#xff0c;欢迎沟通交流&#xff01;期待与您在学习编程的道路上共同进步。 目录 一. 直流电机模块介绍 1.直流电机介绍 2.电机参数 二. 程序设计…

Oracle 直接路径插入(Direct-Path Insert)

直接路径插入&#xff08;Direct Path Insert&#xff09;是Oracle一种数据加载提速技术&#xff0c;可以在使用insert语句或SQL*Loader工具大批量加载数据时使用。直接路径插入处理策略与普通insert语句完全不同&#xff0c;Oracle会通过牺牲空间&#xff0c;安全性&#xff0…

防御保护:防火墙内容安全

一、IAE&#xff08;Intelligent Awareness Engine&#xff09;引擎 二、深度检测技术(DFI和DPI&#xff09; 1.DPI – 深度包检测技术 DPI主要针对完整的数据包&#xff08;数据包分片&#xff0c;分段需要重组&#xff09;&#xff0c;之后对数据包的内容进行识别。&#x…

2024年阿里云2核4G云服务器性能如何?价格便宜有点担心

阿里云2核4G服务器多少钱一年&#xff1f;2核4G服务器1个月费用多少&#xff1f;2核4G服务器30元3个月、85元一年&#xff0c;轻量应用服务器2核4G4M带宽165元一年&#xff0c;企业用户2核4G5M带宽199元一年。本文阿里云服务器网整理的2核4G参加活动的主机是ECS经济型e实例和u1…

第三节-docker-cs架构分析

一、组成 docker engine&#xff1a;docker-client、rest-api、dockerd containerd&#xff1a; 1、管理容器生命周期 2、拉取/推送镜像 3、存储管理 4、调用runc 5、管理网络 containerd-shim&#xff1a;相当于一个驱动&#xff0c;containerd通过containerd-shim驱使…

SpringCloudNacos配置管理及热更新

文章目录 统一配置管理在nacos中添加配置文件从微服务拉取配置配置热更新方式1方式2 配置优先级 之前对 Nacos注册中心入门 已经做了演示. 这篇文章对 Nacos 的服务分级存储模型做理论与实践. 本篇文章阐述 Nacos 做配置中心的理论和实践. 统一配置管理 当微服务部署的实例越…

Vue NextTick工作原理及使用场景

$nextTick的定义及理解&#xff1a; 定义&#xff1a;在下次 DOM 更新循环结束之后执行延迟回调。在修改数据之后立即使用这个方法&#xff0c;获取更新后的 DOM。 所以就衍生出了这个获取更新后的DOM的Vue方法。所以放在Vue.nextTick()回调函数中的执行的应该是会对DOM进行操…

热点参数流控(Sentinel)

热点参数流控 热点流控 资源必须使用注解 SentinelResource 编写接口 以及 热点参数流控处理器 /*** 热点流控 必须使用注解 SentinelResource* param id* return*/ RequestMapping("/getById/{id}") SentinelResource(value "getById", blockHandler …

Media Encoder 2024 for Mac v24.2.1中文激活版

Adobe Media Encoder 2024 for Mac 是一款专业的视频和音频编码工具&#xff0c;专为 Mac 用户打造。它可以将原始素材转换为各种流行格式&#xff0c;以满足不同的播放和发布需求。借助其先进的编码技术和预设设置&#xff0c;用户可以轻松优化输出质量&#xff0c;同时保持文…

森林监测VR虚拟情景再现系统更便利

AI人工智能技术已经逐渐渗透到各个领域&#xff0c;为我们的生活带来了诸多便利。在虚拟仿真教学领域&#xff0c;AI技术的应用也日益丰富&#xff0c;为虚拟情景交互体验带来了前所未有的好处。 提高VR虚拟情景的逼真度 通过深度学习和计算机视觉等技术&#xff0c;AI/VR虚拟现…