javaeye的一個(gè)帖子介紹一道
面試題，取數(shù)組的最大元素和前n個(gè)大元素，取最大元素很簡(jiǎn)單，遍歷即可。取前N大元素，可以利用排序，最簡(jiǎn)單的實(shí)現(xiàn)：
public static int[] findTopNValues(int[] anyOldOrderValues, int n) {
Arrays.sort(anyOldOrderValues);
int[] result = new int[n];
System.arraycopy(anyOldOrderValues, anyOldOrderValues.length - n,
result, 0, n);
return result;
}
Arrays.sort(int[])使用的是快排，平均的時(shí)間復(fù)雜度是O( n lg(n))，在一般情況下已經(jīng)足夠好。那么有沒(méi)有平均情況下O(n)復(fù)雜度的算法？這個(gè)還是有的，這道題目其實(shí)是選擇算法的變形，選擇一個(gè)數(shù)組中的第n大元素，可以采用類(lèi)似快排的方式劃分?jǐn)?shù)組，然后只要在一個(gè)子段做遞歸查找就可以，平均狀況下可以做到O(n)的時(shí)間復(fù)雜度，對(duì)于這道題來(lái)說(shuō)稍微變形下算法即可解決：
/**
* 求數(shù)組的前n個(gè)元素
*
* @param anyOldOrderValues
* @param n
* @return
*/
public static int[] findTopNValues(int[] anyOldOrderValues, int n) {
int[] result = new int[n];
findTopNValues(anyOldOrderValues, 0, anyOldOrderValues.length - 1, n,
n, result);
return result;
}
public static final void findTopNValues(int[] a, int p, int r, int i,
int n, int[] result) {
// 全部取到，直接返回
if (i == 0)
return;
// 只剩一個(gè)元素，拷貝到目標(biāo)數(shù)組
if (p == r) {
System.arraycopy(a, p, result, n - i, i);
return;
}
int len = r - p + 1;
if (i > len || i < 0)
throw new IllegalArgumentException();
// if (len < 7) {
// Arrays.sort(a, p, r+1);
// System.arraycopy(a, r - i+1 , result, n - i, i);
// return;
// }
// 劃分
int q = medPartition(a, p, r);
// 計(jì)算右子段長(zhǎng)度
int k = r - q + 1;
// 右子段長(zhǎng)度恰好等于i
if (i == k) {
// 拷貝右子段到結(jié)果數(shù)組，返回
System.arraycopy(a, q, result, n - i, i);
return;
} else if (k > i) {
// 右子段比i長(zhǎng)，遞歸到右子段求前i個(gè)元素
findTopNValues(a, q + 1, r, i, n, result);
} else {
// 右子段比i短，拷貝右子段到結(jié)果數(shù)組，遞歸左子段求前i-k個(gè)元素
System.arraycopy(a, q, result, n - i, k);
findTopNValues(a, p, q - 1, i - k, n, result);
}
}
public static int medPartition(int x[], int p, int r) {
int len = r - p + 1;
int m = p + (len >> 1);
if (len > 7) {
int l = p;
int n = r;
if (len > 40) { // Big arrays, pseudomedian of 9
int s = len / 8;
l = med3(x, l, l + s, l + 2 * s);
m = med3(x, m - s, m, m + s);
n = med3(x, n - 2 * s, n - s, n);
}
m = med3(x, l, m, n); // Mid-size, med of 3
}
if (m != r) {
int temp = x[m];
x[m] = x[r];
x[r] = temp;
}
return partition(x, p, r);
}
private static int med3(int x[], int a, int b, int c) {
return x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
: x[b] > x[c] ? b : x[a] > x[c] ? c : a;
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static int partition(int a[], int p, int r) {
int x = a[r];
int m = p - 1;
int j = r;
while (true) {
do {
j--;
} while (j>=p&&a[j] > x);
do {
m++;
} while (a[m] < x);
if (j < m)
break;
swap(a, m, j);
}
swap(a, r, j + 1);
return j + 1;
}
選擇算法還有最壞情況下O(n)復(fù)雜度的實(shí)現(xiàn)，有興趣可以讀算法導(dǎo)論和
維基百科。題外，我測(cè)試了下這兩個(gè)實(shí)現(xiàn)，在我的機(jī)器上大概有2倍多的差距，還是很明顯。