【算法】线性时间复杂度的查找算法
文章目录
给定一无序数组a[],求第k小的数
public static int randomPartition(int a[], int low, int high) {
int len = high - low + 1;
Random rand = new Random();
int r = rand.nextInt(len) + low;
int temp = a[r];
a[r] = a[high];
a[high] = temp;
int i = low - 1, j = low;
int key = a[high];
for (; j < high; j++) {
if (a[j] <= key) {
i++;
int temp1 = a[j];
a[j] = a[i];
a[i] = temp1;
}
}
i++;
a[j] = a[i];
a[i] = key;
return i;
}
public static int randomSelect(int a[], int low, int high, int i) {
if (low == high) {
return a[low];
}
int q = randomPartition(a, low, high);
int k = q - low + 1;
if (i == k)
return a[q];
else if (i < k)
return randomSelect(a, low, q - 1, i);
else
return randomSelect(a, q + 1, high, i - k);
}时间复杂度O(n)
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论