Leetcode215-数组中的第K个最大元素

爱被打了一巴掌 2022-09-03 10:27 115阅读 0赞

# 数组中的第K个最大元素 #

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。  
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。  
示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
    输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
    输出: 4

**解题思路**:要返回一个乱序数组的第k大元素,首先对数组进行排序.对数组排序好之后,可以直接取数组下标第k大的元素.这里考虑使用快速排序对数组进行排序.

class Solution { 
        public int findKthLargest(int[] nums, int k) { 
            quickSort(nums);
            return nums[nums.length-k];
        }
        private  void quickSort(int[] nums){ 
            if(nums.length!=0){ 
                subSort(nums,0,nums.length-1);
            }
        }
        private  void subSort(int[] nums,int start,int end){ 
            if(start<end){ 
                int base=nums[start];
                int i=start;
                int j=end+1;                ///+1
                while(true){ 
                    while(i<end && nums[++i]<=base);
                    while(j>start && nums[--j]>=base);
                    if(i<j){ 
                        swap(nums,i,j);
                    }else{ 
                        break;
                    }
                }
                swap(nums,start,j);
                subSort(nums,start,j-1);
                subSort(nums,j+1,end);
            }
        }
        private  void swap(int[] nums,int start,int end){ 
            int temp=nums[start];
            nums[start]=nums[end];
            nums[end]=temp;
        }
    }

另一个版本的快排，哪种熟悉用哪种：

class Solution { 
        public int findKthLargest(int[] nums, int k) { 
            quickSort(nums,0,nums.length-1);
            return nums[nums.length-k];
        }
        public void quickSort(int[] nums,int start,int end){ 
            if(start>end) return;
            int i,j,base;
            i=start;
            j=end;
            base=nums[start];//第一个元素作为基准
            while(i<j){ 
                while(nums[j]>=base && i<j){  j--;} //先移动右指针
                while(nums[i]<=base && i<j){  i++;} 
                if(i<j){ 
                    swap(nums,i,j);
                }
            }
            //循环完之后i和j移动到相同的位置
            //将基准调到i和j相等的位置
            swap(nums,start,i);
            //i和j相遇的位置左边递归
            quickSort(nums,start,j-1);
            //i和j相遇的位置右边递归
            quickSort(nums,j+1,end);
        }
        public void swap(int[] nums,int left,int right){ 
            int temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
        }
    
    }