数组中第K大的数

迈不过友情╰ 2022-12-21 04:51 126阅读 0赞

**题目描述**  
有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

示例1
    输入
    [1,3,5,2,2],5,3
    返回值
    2

import java.util.*;
    
    public class Finder {
        
        public int findKth(int[] a, int n, int K) {
        
            // write code here
            //思想：快排+二分法利用快排在排序时，把数组分成两部分 
            //选temp 值为a[start],经过一轮后 数组左边的值小于或者等于temp,数组右边的所有值都大于或等于temp
           //假设此时 i整好等于k,那么temp就是第K大的值
           //如果i大于k,那么说明第K大值在数组左边，则继续在左边查找
          //如果i小于k,那么说明第K大值在数组的右边，继续在右边查找
             return quickSort(a, 0, n - 1, K);
        }
        public int quickSort(int[] a, int start, int end, int k){
        
            int temp=a[start];
            int s=start,e=end;
            while(s<e){
        
                while(s<e && temp >=a[e]) e--;
                    a[s]=a[e];
                while(s<e && temp<=a[s]) s++;
                    a[e]=a[s];
            }
            a[s]=temp;
            if(s==k-1){
        
                return a[s];
            }else if(s > k-1){
        
                return quickSort(a, start,s-1,k);
            }else{
        
                return quickSort(a, s+1, end, k);
            }
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，126人围观）

还没有评论，来说两句吧...

相关阅读

相关找出数组中第k大的数

package com.threeTop.www; /** * 找出数组中第k大的数 * @author wjgs ...

╰半夏微凉°/ 2024年04月17日 14:47/ 0 赞/ 25 阅读

相关数组中的第K个最大元素

215. 数组中的第K个最大元素 > 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 > 请注意，你需要找的是数组排序后的第 k 个最大的元素，

- 日理万妓/ 2024年04月06日 11:56/ 0 赞/ 28 阅读

相关找出数组中的第K大的数或者第K小的数

class Solution { public: int findKthLargest(vector<int>& res, int k)

本是古典何须时尚/ 2022年12月31日 01:25/ 0 赞/ 138 阅读

相关数组中第K大的数

题目描述有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存

迈不过友情╰/ 2022年12月21日 04:51/ 0 赞/ 127 阅读

相关寻找第 K 大的数

寻找第 K 大的数 1、参考资料 https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

爱被打了一巴掌/ 2022年12月05日 04:51/ 0 赞/ 185 阅读

相关寻找第k大or第k小的数--＞寻找中位数

> 快排思想，选取数组中第一个元素e为参考元素，利用partition() 使得数组左边的元素全都不大于e，数组右边的元素全都不小于e–>升序排序 > 设数组长度为n，若e的

Love The Way You Lie/ 2022年11月29日 11:27/ 0 赞/ 152 阅读

相关求一个数组中第k大的数方法

求一个数组中第k大的数，我第一印象是冒泡，因为只要冒泡k趟即可，第一趟冒泡第一大，第二次冒泡第二大，第k次冒泡第k大，时间复杂度为O(kn),n为数组长度。但是我们都知道快速排

忘是亡心i/ 2022年09月26日 02:24/ 0 赞/ 133 阅读

相关寻找第K大的数

1，对于一个有序数组则为第K个数，O（1） 2，对于一个无序数组使用修改的快排划分算法，时间复杂度为O（n） 3，对于两个无序数组

小咪咪/ 2022年05月21日 03:20/ 0 赞/ 142 阅读

相关数组中任意第k大的数字

模仿partion方法，当high=low小于k的时候，在后半部分搜索，当high=low大于k的时候，在前半部分搜索。与快排不同的是，每次都减少了一半的排序。 de

电玩女神/ 2022年04月14日 06:53/ 0 赞/ 143 阅读

相关【数据结构与算法】寻找无序数组中第K大的数

寻找无序数组中第K大的数方法1：排序法方法2：插入法方法3：小顶堆法方法4：分治法部分参考： [漫画：寻找无序数组的第K大元

女爷i/ 2022年01月20日 14:27/ 0 赞/ 187 阅读