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

2024-01-04 18:04
文章标签 数组 元素 最大 lcr 076

本文主要是介绍LCR 076. 数组中的第 K 个最大元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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


题目链接:LCR 076. 数组中的第 K 个最大元素

下面这个题与这个题一样:

题目链接:215. 数组中的第K个最大元素

这个代码只能通过第一个题,如下:

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {quickSort(nums,0,nums.size()-1);return nums[nums.size()-k];}//快速排序void quickSort(vector<int>& nums,int low,int high){if(low>=high)return;int partitionpivot=partition(nums,low,high);quickSort(nums,low,partitionpivot-1);quickSort(nums,partitionpivot+1,high);}int partition(vector<int>&nums,int low,int high){int temp=nums[low];  while(low<high){while(low<high&&nums[high]>=temp)high--;swap(nums[low],nums[high]);while(low<high&&nums[low]<=temp)low++;swap(nums[low],nums[high]);}nums[low]=temp;return low;}
};

这个代码两个题都能通过,如下:

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {vector<int> temp;temp.push_back(0);for(int i=0;i<nums.size();i++){temp.push_back(nums[i]);}HeapSort(temp,nums.size());return temp[temp.size()-k];}//在含有n个元素的堆中添加一个元素,并调整为堆void HeadAdjust(vector<int>& arr, int i, int n)//调整为大根堆{arr[0] = arr[i];for (int j = 2 * i; j <= n; j *= 2){if (j < n && arr[j] < arr[j + 1])j++;if (arr[j] <= arr[0])break;else{arr[i] = arr[j];i = j;}}arr[i] = arr[0];}void HeapSort(vector<int>& arr, int n)//递增排序{for (int i = n / 2; i > 0; i--)HeadAdjust(arr, i, n);for (int i = n; i > 1; i--){swap(arr[1], arr[i]);HeadAdjust(arr, 1, i - 1);}}
};

这篇关于LCR 076. 数组中的第 K 个最大元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/570138

相关文章

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制

vue如何监听对象或者数组某个属性的变化详解

《vue如何监听对象或者数组某个属性的变化详解》这篇文章主要给大家介绍了关于vue如何监听对象或者数组某个属性的变化,在Vue.js中可以通过watch监听属性变化并动态修改其他属性的值,watch通... 目录前言用watch监听深度监听使用计算属性watch和计算属性的区别在vue 3中使用watchE

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若