Kth|Kth Largest Element in an Array 数组中第k大的数字 KthLargestElementinanArray数组中第

前言: 头条面试题目, 当时没想出来，现在回想起来如果熟悉快速排序的话也就是分分钟的事情了。不过头条真心重视算法，基本是算法牛逼就铁定过。

在最短的时间内找到第k大数

思路: 快速排序 + 舍弃一半方法，时间复杂度为O(nlogn)

package com.protobuf.ACM; /** * Created by liuchaoqun01 on 2019/1/12. */ public class Klarge {/** * 寻找第k大数,时间复杂度为: O(nlogn) * @param a * @param low * @param high * @param k * @return */ public static int getLeftArray (int[] a, int low, int high, int k) { int i,j,index; if(low > high) { // 递归截止条件 return-1; } index = a[low]; i = low; j = high; while (i < j) { while (i < j && a[j] >= index) { j--; } if (i < j) { a[i++] = a[j]; } while (i < j && a[i] <= index) { i++; } if (i < j) { a[j--] = a[i]; } } // final i == j a[i] = index; // 找到第k大数 if (i == (k-1)) { return index; } if (i > (k -1)) { return getLeftArray(a, low, i - 1, k); } else { return getLeftArray(a, i + 1, high, k); } }/** * 快速排序: O(nlogn) */ public static void sort (int[] a, int low, int high) { int i, j, index; if (low > high) { // 递归截止条件 return; } index = a[low]; i = low; j = high; while (i < j) { while (i < j && a[j] >= index) { j--; } if (i < j) { a[i++] = a[j]; } while (i < j && a[i] <= index) { i++; } if (i < j) { a[j--] = a[i]; } } // final i == j a[i] = index; sort(a, low, i - 1); sort(a, i + 1, high); }public static void main(String[] args) { int[] arr = {2,34,1,22,9}; sort(arr, 0, arr.length -1); int res = getLeftArray(arr, 0, arr.length - 1, 4); System.out.println(res); } }