Java中位数的中位数
我正在尝试使用Java实现这样的方法中的Median Median：
Select(Comparable[] list, int pos, int colSize, int colMed) -
list是要查找指定位置的值列表 -
pos是指定的位置 -
colSize是我在第一阶段创建的列的大小 -
colMed是我用作medX的那些列中的位置
我不确定哪种排序算法最适合使用或如何实现这一点。
我不知道你是否仍然需要解决这个问题，但http://www.ics.uci.edu/~eppstein/161/960130.html有一个算法：
select(L,k) { if (L has 10 or fewer elements) { sort L return the element in the kth position } partition L into subsets S[i] of five elements each (there will be n/5 subsets total). for (i = 1 to n/5) do x[i] = select(S[i],3) M = select({x[i]}, n/10) partition L into L1M if (k <= length(L1)) return select(L1,k) else if (k > length(L1)+length(L2)) return select(L3,k-length(L1)-length(L2)) else return M }
祝你好运！
这个问题要求Java，所以在这里
import java.util.*; public class MedianOfMedians { private MedianOfMedians() { } /** * Returns median of list in linear time. * * @param list list to search, which may be reordered on return * @return median of array in linear time. */ public static Comparable getMedian(ArrayList list) { int s = list.size(); if (s < 1) throw new IllegalArgumentException(); int pos = select(list, 0, s, s / 2); return list.get(pos); } /** * Returns position of k'th largest element of sub-list. * * @param list list to search, whose sub-list may be shuffled before * returning * @param lo first element of sub-list in list * @param hi just after last element of sub-list in list * @param k * @return position of k'th largest element of (possibly shuffled) sub-list. */ public static int select(ArrayList list, int lo, int hi, int k) { if (lo >= hi || k < 0 || lo + k >= hi) throw new IllegalArgumentException(); if (hi - lo < 10) { Collections.sort(list.subList(lo, hi)); return lo + k; } int s = hi - lo; int np = s / 5; // Number of partitions for (int i = 0; i < np; i++) { // For each partition, move its median to front of our sublist int lo2 = lo + i * 5; int hi2 = (i + 1 == np) ? hi : (lo2 + 5); int pos = select(list, lo2, hi2, 2); Collections.swap(list, pos, lo + i); } // Partition medians were moved to front, so we can recurse without making another list. int pos = select(list, lo, lo + np, np / 2); // Re-partition list to [pivot] int m = triage(list, lo, hi, pos); int cmp = lo + k - m; if (cmp > 0) return select(list, m + 1, hi, k - (m - lo) - 1); else if (cmp < 0) return select(list, lo, m, k); return lo + k; } /** * Partition sub-list into 3 parts [pivot]. * * @param list * @param lo * @param hi * @param pos input position of pivot value * @return output position of pivot value */ private static int triage(ArrayList list, int lo, int hi, int pos) { Comparable pivot = list.get(pos); int lo3 = lo; int hi3 = hi; while (lo3 < hi3) { Comparable e = list.get(lo3); int cmp = e.compareTo(pivot); if (cmp < 0) lo3++; else if (cmp > 0) Collections.swap(list, lo3, --hi3); else { while (hi3 > lo3 + 1) { assert (list.get(lo3).compareTo(pivot) == 0); e = list.get(--hi3); cmp = e.compareTo(pivot); if (cmp <= 0) { if (lo3 + 1 == hi3) { Collections.swap(list, lo3, lo3 + 1); lo3++; break; } Collections.swap(list, lo3, lo3 + 1); assert (list.get(lo3 + 1).compareTo(pivot) == 0); Collections.swap(list, lo3, hi3); lo3++; hi3++; } } break; } } assert (list.get(lo3).compareTo(pivot) == 0); return lo3; } }
这是一个unit testing来检查它的工作原理......
import java.util.*; import junit.framework.TestCase; public class MedianOfMedianTest extends TestCase { public void testMedianOfMedianTest() { Random r = new Random(1); int n = 87; for (int trial = 0; trial < 1000; trial++) { ArrayList list = new ArrayList(); int[] a = new int[n]; for (int i = 0; i < n; i++) { int v = r.nextInt(256); a[i] = v; list.add(v); } int m1 = (Integer)MedianOfMedians.getMedian(list); Arrays.sort(a); int m2 = a[n/2]; assertEquals(m1, m2); } } }
但是，上述代码对于实际使用来说太慢了。
这是一种更简单的方法来获得不保证性能的第k个元素，但在实践中要快得多：
/** * Returns position of k'th largest element of sub-list. * * @param list list to search, whose sub-list may be shuffled before * returning * @param lo first element of sub-list in list * @param hi just after last element of sub-list in list * @param k * @return position of k'th largest element of (possibly shuffled) sub-list. */ static int select(double[] list, int lo, int hi, int k) { int n = hi - lo; if (n < 2) return lo; double pivot = list[lo + (k * 7919) % n]; // Pick a random pivot // Triage list to [pivot] int nLess = 0, nSame = 0, nMore = 0; int lo3 = lo; int hi3 = hi; while (lo3 < hi3) { double e = list[lo3]; int cmp = compare(e, pivot); if (cmp < 0) { nLess++; lo3++; } else if (cmp > 0) { swap(list, lo3, --hi3); if (nSame > 0) swap(list, hi3, hi3 + nSame); nMore++; } else { nSame++; swap(list, lo3, --hi3); } } assert (nSame > 0); assert (nLess + nSame + nMore == n); assert (list[lo + nLess] == pivot); assert (list[hi - nMore - 1] == pivot); if (k >= n - nMore) return select(list, hi - nMore, hi, k - nLess - nSame); else if (k < nLess) return select(list, lo, lo + nLess, k); return lo + k; }
我同意Chip Uni的答案/解决方案。 我将只评论排序部分并提供一些进一步的解释：
您不需要任何排序算法。 该算法类似于快速排序，区别在于只有一个分区被解决（左或右）。 我们只需找到一个最佳枢轴，使左右部分尽可能相等，这意味着N / 2 + N / 4 + N / 8 … = 2N迭代，因此O（N的时间复杂度） ）。 上述算法称为中位数中位数，计算中位数的中位数为5，结果certificate算法的线性时间复杂度。
但是，当搜索范围为第n个最小/最大元素（我想您正在使用此算法实现）时，使用排序算法以加速算法。 插入排序在最多7到10个元素的小arrays上特别快。
实施说明：
M = select({x[i]}, n/10)
实际上意味着取5个元素组的所有中位数的中位数。 您可以通过创建另一个大小为(n - 1)/5 + 1数组并以递归方式调用相同的算法来查找第n / 10个元素（这是新创建的数组的中位数）来实现这一点。
@android开发者：
for (i = 1 to n/5) do x[i] = select(S[i],3)
是真的
for (i = 1 to ceiling(n/5) do x[i] = select(S[i],3)
具有适合于您的数据的上限函数（例如，在java 2中）这会影响中位数以及简单地取n / 10，但我们发现最接近数组中出现的均值，而不是真正的均值。 另一个注意事项是S [i]可能少于3个元素，因此我们希望找到相对于长度的中位数; 将其传递给k = 3的select并不总是有效。（例如n = 11，我们有3个子组2 w 5,1 w 1个元素）
我知道这是一个非常古老的post，你可能不再记得了。 但我想知道你实施它时是否衡量了实施的运行时间？
我尝试了这个算法并将其与使用java排序方法（Arrays.sort（））的简单方法进行比较，然后从排序数组中选择第k个元素。 我收到的结果是，当数组的大小大约是十万或更多元素时，这种算法只能胜过java排序算法。 而且它只快2到3倍，显然不是log（n）时间更快。
你有什么评论吗？