找到数组的中值?

我想知道是否有可能找到数组的中值? 例如,假设我有一个大小为9的数组。 是否有可能找到这个arrays的中间槽?

假设数组x已排序且长度为n

如果n是奇数,那么中值是x [(n-1)/ 2]。
如果n是偶数,则中值是(x [n / 2] + x [(n / 2)-1])/ 2。

如果你想在这里使用任何外部库,那么Apache commons数学库可以用来计算中位数 。
有关更多方法和用法,请参阅API文档

import org.apache.commons.math3.*; ..... ...... ........ //calculate median public double getMedian(double[] values){ Median median = new Median(); double medianValue = median.evaluate(values); return medianValue; } ....... 
  • 有关评估方法AbstractUnivariateStatistic#evaluate的更多信息

在程序中计算

通常,使用此处给出的以下两个公式计算中值

如果n是奇数,那么中位数(M)=((n + 1)/ 2)项项的值。
如果n是偶数,则中位数(M)= [((n)/ 2)项项的值+((n)/ 2 + 1)项项目] / 2

这很容易,因为你有9个元素(奇数)。
找到数组的中间元素。
在你的程序中,你可以声明数组

 //as you mentioned in question, you have array with 9 elements int[] numArray = new int[9]; 

那么你需要使用Arrays排序数组#sorted

 Arrays.sort(numArray); int middle = numArray.length/2; int medianValue = 0; //declare variable if (numArray.length%2 == 1) medianValue = numArray[middle]; else medianValue = (numArray[middle-1] + numArray[middle]) / 2; 

在java中:

 int middleSlot = youArray.length/2; yourArray[middleSlot]; 

要么

 yourArray[yourArray.length/2]; 

在一行。

这是可能的,因为在java数组中有一个固定的大小。

注意: 3/2 == 1


资源:

  • Java教程 – 数组

在C ++中,您可以使用std::nth_element ; 请参阅http://cplusplus.com/reference/algorithm/nth_element/ 。

 vector v; size_t len = v.size; nth_element( v.begin(), v.begin()+len/2,v.end() ); int median = v[len/2]; 

上面的Java答案只有在这里有一个奇怪的数字是我得到解决方案的答案时才有效:

 if (yourArray.length % 2 == 0){ //this is for if your array has an even ammount of numbers double middleNumOne = yourArray[yourArray.length / 2 - 0.5] double middleNumTwo = yourArray[yourArray.length / 2 + 0.5] double median = (middleNumOne + middleNumTwo) / 2; System.out.print(median); }else{ //this is for if your array has an odd ammount of numbers System.out.print(yourArray[yourArray.length/2];); } 

请注意,这是一个概念certificate和即时。 如果您认为可以使其更紧凑或更少密集,请继续前进。 请不要批评它。

还有另一种选择 – 一般来说,这里的建议要么建议对数组进行排序,然后从这样的数组中获取中值,要么依赖于(外部)库解决方案。 今天最快的排序算法平均而言是线性的,但是为了中值计算的目的,它可能比这更好。

从未排序数组计算中值的最快算法是QuickSelect ,它平均可以找到与O(N)成比例的时间中位数。 该算法将数组作为参数,与int值k (顺序统计量,即数组中的第k个最小元素)一起使用。 在这种情况下, k的值仅为N / 2,其中N是数组长度。

实现起来并不是很难解决,但这里有一个依赖于Comparable接口和Collections.shuffle()而没有任何外部依赖性的例子。

 public final class QuickSelectExample { public static > T select(T[] a, int k) { if (k < 1) throw new IllegalStateException("Invalid k - must be in [1, inputLength]."); if (k > a.length) throw new IllegalStateException("K-th element exceeds array length."); Collections.shuffle(Arrays.asList(a)); return find(a, 0, a.length - 1, k - 1); } private static > T find(T[] a, int lo, int hi, int k) { int mid = partition(a, lo, hi); if (k == mid) return a[k]; else if (k < mid) return find(a, lo, mid - 1, k); // search left subarray else if (k > mid) return find(a, mid + 1, hi, k); // search right subarray else throw new IllegalStateException("Not found"); } private static > int partition(T[] a, int lo, int hi) { T pivot = a[lo]; int i = lo + 1; int j = hi; while (true) { // phase 1 while (i <= hi && (less(a[i], pivot) || eq(a[i], pivot))) // is a[i] >= pivot? i++; while (j >= i && !less(a[j], pivot)) // is a[j] <= pivot? j--; if (i >= j) break; exch(a, i, j); } exch(a, lo, j); // phase 2 return j; } private static > boolean less(T x, T y) { return x.compareTo(y) < 0; } private static > boolean eq(T x, T y) { return x.compareTo(y) == 0; } } 

该代码为这些输入数组生成以下顺序统计信息:

  " Input Array | Actual Output [format: (index k -> array element)] ", // " | ", // " [S, O, R, T, E, X, A, M, P, L, E] | [(1 -> A), (2 -> E), (3 -> E), (4 -> L), (5 -> M), (6 -> O), (7 -> P), (8 -> R), (9 -> S), (10 -> T), (11 -> X)] ", // " [P, A, B, X, W, P, P, V, P, D, P, C, Y, Z] | [(1 -> A), (2 -> B), (3 -> C), (4 -> D), (5 -> P), (6 -> P), (7 -> P), (8 -> P), (9 -> P), (10 -> V), (11 -> W), (12 -> X), (13 -> Y), (14 -> Z)] " // 

像专业人士一样在一行中做到:

 return (arr[size/2] + arr[(size-1)/2]) / 2; 

如果你期待一个double等等,就投double