24.随机选择算法

大家好，欢迎来到IT知识分享网。

问题描述：

算法思想：

代码如下：

// 无序数组中第K大的元素 // 测试链接 : https://leetcode.cn/problems/kth-largest-element-in-an-array/ public class RandomizedSelect { 
    // 随机选择算法，时间复杂度O(n) public static int findKthLargest(int[] nums, int k) { 
    return randomizedSelect(nums, nums.length - k); } // 如果arr排序的话，在i位置的数字是什么 public static int randomizedSelect(int[] arr, int i) { 
    int ans = 0; for (int l = 0, r = arr.length - 1; l <= r;) { 
    // 随机这一下，常数时间比较大 // 但只有这一下随机，才能在概率上把时间复杂度收敛到O(n) partition(arr, l, r, arr[l + (int) (Math.random() * (r - l + 1))]); // 因为左右两侧只需要走一侧 // 所以不需要临时变量记录全局的first、last // 直接用即可 if (i < first) { 
    r = first - 1; } else if (i > last) { 
    l = last + 1; } else { 
    ans = arr[i]; break; } } return ans; } // 荷兰国旗问题 public static int first, last; public static void partition(int[] arr, int l, int r, int x) { 
    first = l; last = r; int i = l; while (i <= last) { 
    if (arr[i] == x) { 
    i++; } else if (arr[i] < x) { 
    swap(arr, first++, i++); } else { 
    swap(arr, i, last--); } } } public static void swap(int[] arr, int i, int j) { 
    int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }