中位数 select 算法的中位数
Median of medians select algorithm
在过去的几天里,我一直在努力编写这个算法,但没有成功。该代码有效,大多数时候它会给我正确的结果,但在某些情况下它会失败。例如,对于这个数组 {3, 8, 1, 9, 10, 7, 6, 2, 5, 4} 和 k = 6 它应该给我 6 作为结果但它给了我 7。有人可以帮助我吗?我不知道是什么问题。
代码如下:
class MOMSelect {
static int median(int a[], int i, int n) {
if(i <= n)
Arrays.sort(a, i, n);
else
Arrays.sort(a, n, i);
return a[n/2];
}
static int medianOfMediansSelect(int a[], int left, int right, int k) {
int n = right - left + 1;
int i;
int[] medians = new int[(n + 4) / 5];
for (i = 0; i < n/5; i++) {
medians[i] = median(a, left + i * 5, 5);
}
if (i*5 < n) {
medians[i] = median(a,left + i * 5, n % 5);
i++;
}
int medianOfMedians = (i == 1)? medians[i - 1]: median(medians, 0, medians.length);
int pivotIndex = partition(a, left, right, medianOfMedians);
if (pivotIndex == k - 1) {
return a[pivotIndex];
}
else if (pivotIndex - left > k - 1) {
return medianOfMediansSelect(a, left, pivotIndex - 1, k);
}
else {
return medianOfMediansSelect(a, pivotIndex + 1, right, k);
}
}
static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
static int partition(int[] a, int left, int right, int x) {
int i;
for (i = left; i < right; i++)
if (a[i] == x)
break;
swap(a, i, right);
i = left;
for (int j = left; j <= right - 1; j++) {
if(a[j] <= x) {
swap(a, i, j);
i++;
}
}
swap(a, i, right);
return i;
}
public static void main(String[] args) {
int a[] = {3, 8, 1, 9, 10, 7, 6, 2, 5, 4};
int n = a.length;
int k = 1;
System.out.println(medianOfMediansSelect(a, 0, n - 1, k));
}
}
在此先感谢大家
所以,我修改了您的 median
方法来解决问题。您应该检查 Arrays.sort
方法以获得清晰的理解。
现在它给出 6
,因为 k=6
。
就在这里,
static int median(int a[], int i, int n)
{
Arrays.sort(a, i, i + n - 1);
return a[i + n / 2];
}
好的,我解决了。除了我对 Arrays.sort() 方法的错误理解外,在 if 结构上还有一个愚蠢的错误,我在该结构上检查了方法 medianOfMediansSelect()
上的 pivotPosition 值
更准确地说是这条线
else if (pivotIndex - left > k - 1) {
我应该这样做
else if (pivotIndex > k - 1) {
在过去的几天里,我一直在努力编写这个算法,但没有成功。该代码有效,大多数时候它会给我正确的结果,但在某些情况下它会失败。例如,对于这个数组 {3, 8, 1, 9, 10, 7, 6, 2, 5, 4} 和 k = 6 它应该给我 6 作为结果但它给了我 7。有人可以帮助我吗?我不知道是什么问题。
代码如下:
class MOMSelect {
static int median(int a[], int i, int n) {
if(i <= n)
Arrays.sort(a, i, n);
else
Arrays.sort(a, n, i);
return a[n/2];
}
static int medianOfMediansSelect(int a[], int left, int right, int k) {
int n = right - left + 1;
int i;
int[] medians = new int[(n + 4) / 5];
for (i = 0; i < n/5; i++) {
medians[i] = median(a, left + i * 5, 5);
}
if (i*5 < n) {
medians[i] = median(a,left + i * 5, n % 5);
i++;
}
int medianOfMedians = (i == 1)? medians[i - 1]: median(medians, 0, medians.length);
int pivotIndex = partition(a, left, right, medianOfMedians);
if (pivotIndex == k - 1) {
return a[pivotIndex];
}
else if (pivotIndex - left > k - 1) {
return medianOfMediansSelect(a, left, pivotIndex - 1, k);
}
else {
return medianOfMediansSelect(a, pivotIndex + 1, right, k);
}
}
static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
static int partition(int[] a, int left, int right, int x) {
int i;
for (i = left; i < right; i++)
if (a[i] == x)
break;
swap(a, i, right);
i = left;
for (int j = left; j <= right - 1; j++) {
if(a[j] <= x) {
swap(a, i, j);
i++;
}
}
swap(a, i, right);
return i;
}
public static void main(String[] args) {
int a[] = {3, 8, 1, 9, 10, 7, 6, 2, 5, 4};
int n = a.length;
int k = 1;
System.out.println(medianOfMediansSelect(a, 0, n - 1, k));
}
}
在此先感谢大家
所以,我修改了您的 median
方法来解决问题。您应该检查 Arrays.sort
方法以获得清晰的理解。
现在它给出 6
,因为 k=6
。
就在这里,
static int median(int a[], int i, int n)
{
Arrays.sort(a, i, i + n - 1);
return a[i + n / 2];
}
好的,我解决了。除了我对 Arrays.sort() 方法的错误理解外,在 if 结构上还有一个愚蠢的错误,我在该结构上检查了方法 medianOfMediansSelect()
更准确地说是这条线
else if (pivotIndex - left > k - 1) {
我应该这样做
else if (pivotIndex > k - 1) {