题目描述

样例

算法1

(quick sort) $O(n)$

import java.util.*;
public class Main{

public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int k = scanner.nextInt();
    int q[] = new int[n];
    for (int i = 0; i < n; i++) q[i] = scanner.nextInt();
    System.out.println(quickSelect(q, 0, n-1, k-1));
}

private static int quickSelect(int[] arr, int start, int end, int k){
    if(start >= end) return arr[start];
    Random random_num = new Random();
    int pivot_index = start + random_num.nextInt(end - start);
    int key = partition(arr, start, end, pivot_index);
    if(key > k){
        return quickSelect(arr, start, key-1, k);
    }else if(key < k){
        return quickSelect(arr, key+1, end, k);
    }else {
        return arr[k];
    }
}

private static int partition(int[] arr, int start, int end,int pivot_index ){
    int pivot = arr[pivot_index];
    swap(pivot_index, start, arr);
    while(start < end){
        while(start < end && arr[end] >= pivot){
            end--;
        }
        arr[start] = arr[end];
        while(start < end && arr[start] <= pivot){
            start++;
        }
        arr[end] = arr[start];
    } 
    arr[start] = pivot;
    return start;
}

 public static void swap(int a, int b, int[] nums) {
    int tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
}

}

时间复杂度

linear