LeetCode 215题数组中第k大元素

╰半夏微凉° 2023-02-21 06:42 126阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]

#### 解法一 ####

使用java自带Arrays.sort()函数并返回

class Solution { 
        public int findKthLargest(int[] nums, int k) { 
            Arrays.sort(nums);
            return nums[nums.length-k];
        }
    }

#### 解法二 ####

使用java自带的优先队列类 PriorityQueue()利用小顶堆的思想，判断size大于k时删除堆中元素，最终堆顶就是第k大元素

class Solution { 
        public int findKthLargest(int[] nums, int k) { 
            final PriorityQueue<Integer> queue = new PriorityQueue<>();
            for(int val : nums){ 
                queue.add(val);
                if(queue.size()>k){ 
                    queue.poll();
                }
            }
            return queue.peek();
        }
    }

#### 解法三 ####

快速排序法

class Solution { 
        public int findKthLargest(int[] nums, int k) { 
            int len = nums.length;
            int left = 0;
            int right = len - 1;
            int target = len - k;
            while(true){ 
            //返回的是nums[left]排序完在数组中的位置
            int index = partition(nums,right,left);
            if(index == target){ 
                return nums[index];
            }
            else if(index < target){ 
                left = index + 1;
            }
            else if(index > target){ 
                right = index - 1;
            }
        }
        }
        //得出nums[left]排序完在数组中的位置
        public int partition(int []nums,int right,int left){ 
            int privot = nums[left];
            int j = left;
            for(int i = left + 1;i<=right;i++){ 
                if(nums[i]<privot){ 
                    j++;
                    swap(nums,j,i);
                }
            }
            //最后要交换一下nums[left]和nums[j]，j是一直同步记录的nums[left]的位置
            swap(nums,j,left);
            return j;
        }
        public void swap(int []nums,int i,int j){ 
            int t = nums[i];
            nums[i]=nums[j];
            nums[j]=t;
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200629150832995.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ==,size_16,color_FFFFFF,t_70