LeetCode 数组中的第K个最大元素【选择排序】

素颜马尾好姑娘i 2022-09-14 15:27 161阅读 0赞

# 1 数组中的第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

提示：

1 <= k <= nums.length <= 104
    -104 <= nums[i] <= 104

# 2 Code #

public class FindKthLargest { 
    
        public int findKthLargest(int[] nums, int k) { 
    
            return selectSort(nums, 0, nums.length - 1, nums.length - k);
        }
    
        private int selectSort(int[] nums, int left, int right, int index) { 
            int select = selectRandomSort(nums, left, right);
            if (select == index) { 
                return nums[select];
            } else { 
                return select > index ? selectSort(nums, left, select - 1, index) : selectSort(nums, select + 1, right, index);
            }
        }
    
        private int selectRandomSort(int[] nums, int left, int right) { 
    
            //找个随机的基数，使index尽可能靠中间
            Random random = new Random();
            int randomIndex = left + random.nextInt(right - left + 1);
            swap(nums, left, randomIndex);
            //简易快排序
            int tempLeft = left;
            int tempRight = right;
            int key = nums[left];
            while (tempLeft < tempRight) { 
                //右边找比key小的
                while (tempLeft < tempRight && nums[tempRight] >= key) { 
                    tempRight--;
                }
                //从左边找比key大的
                while (tempLeft < tempRight && nums[tempLeft] <= key) { 
                    tempLeft++;
                }
    
                if (tempLeft < tempRight) { 
                    swap(nums, tempLeft, tempRight);
                }
    
            }
            swap(nums, left, tempLeft);
            return tempLeft;
        }
    
        private void swap(int[] nums, int i, int j) { 
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    
    
        public static void main(String[] args) { 
    
            FindKthLargest findKthLargest = new FindKthLargest();
            int[] nums1 = new int[]{ 3, 2, 1, 5, 6, 4};
            System.out.println(findKthLargest.findKthLargest(nums1, 2));
    
     
    
        }
    
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/8c23bfb1207848c2b57faaa17d072216.png