前言: 頭條面試題目, 當(dāng)時(shí)沒(méi)想出來(lái)喳钟，現(xiàn)在回想起來(lái)如果熟悉快速排序的話也就是分分鐘的事情了树肃。不過(guò)頭條真心重視算法遍略，基本是算法牛逼就鐵定過(guò)舱卡。
在最短的時(shí)間內(nèi)找到第k大數(shù)
- 思路: 快速排序 + 舍棄一半方法，時(shí)間復(fù)雜度為O(nlogn)
package com.protobuf.ACM;
/**
* Created by liuchaoqun01 on 2019/1/12.
*/
public class Klarge {
/**
* 尋找第k大數(shù),時(shí)間復(fù)雜度為: 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大數(shù)
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);
}
}
- 后記
后來(lái)發(fā)現(xiàn)其實(shí)LeetCode中的題目陪毡，并且有一道相似的題目米母，遂記錄如下勾扭，具體參考2
參考：
1 leetcod: Kth Largest Element in a Stream 數(shù)據(jù)流中的第K大的元素
2 703. Kth Largest Element in a Stream
