leetcode215.数组中的第k个最大元素（快排/堆排序 java）***

た入场券 2023-08-17 17:01 47阅读 0赞

class Solution {
        public int findKthLargest(int[] nums, int k) {
            int len=nums.length;
            int left=0,right=len-1;
            int target=len-k;                                //第k大的元素的数组下标就是len-k，可通过找规律得出
            while(true){
                int index=partition(nums,left,right);       //index用来判断nums[left]排在数组中的第几位大小，并将其移到对应的位置
                if(index==target)
                    return nums[target];
                if(index>target)                         //因为nums[left]比第k大的数大，nums[left]左边的数都比它小，所以使right=index-1.继续接下来的判断
                    right=index-1;
                if(index<target)
                    left=index+1;
            }
        }
    
        public int partition(int[] nums, int left, int right) {
            int pivot=nums[left];
            int j=left;                                   //j用来判断pivot排在数组中的第几个大小位置
            for(int i=left+1;i<=right;i++){
                if(nums[i]<pivot){
                    j++;
                    swap(nums,j,i);
                }
            }
            swap(nums,j,left);
            return j;
        }
    
        private void swap(int[] nums, int index1, int index2) {
            if(index1==index2) return ;
            int temp=nums[index1];
            nums[index1]=nums[index2];
            nums[index2]=temp;
        }
    }

转载于:https://www.cnblogs.com/y1040511302/p/11455788.html