查找数组的中值？

Question

我想知道是否有可能找到数组的中值？例如，假设我有一个大小为9的数组。有可能找到这个阵列的中间插槽吗？

Answer 1

假设阵列X进行排序并且长度Ñ的：

如果n是奇数，则位数为x [（N-1）/ 2]。
如果n是偶数，则中位数为（x [n/2] + x [（n/2）-1]）/ 2.

Answer 2

vector<int> v; 
size_t len = v.size; 
nth_element(v.begin(), v.begin()+len/2,v.end()); 

int median = v[len/2]; 

Answer 3

在java中：

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

或

yourArray[yourArray.length/2]; 

在一行中。

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

注：3/2 == 1

---

资源：

• Java tutorial - Arrays

Answer 4

在C++中，你可以使用std::nth_element;见http://cplusplus.com/reference/algorithm/nth_element/。

Answer 5

上面的Java答案只适用于存在奇怪的ammount这里的数字是我得到的解决方案的答案：

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];); 
} 

并注意这是一个概念证明，并在飞行中。如果你认为你可以让它更紧凑或更密集，那么就直接走吧。请不要批评它。

Answer 6

如果您要使用任何外部库，这里是Apache commons math library使用您可以计算Median。
更多的方法和使用采取看看API documentation

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

计算程序

一般而言，中位数计算使用以下两个公式given here

如果n是奇数，则Median（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#sort

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; 

Answer 7

还有另外一种选择排序阵列 - 在这里一般情况下，建议或者暗示排数组，然后取来自这样的阵列的中位数或依赖（外部）库解决方案。目前最快的排序算法平均来说是线性的，但是为了中位数计算的目的，可以做得更好。

从未排序的数组中计算中位数的最快算法是QuickSelect，平均而言，它可以找到与O（N）成比例的时间中位数。该算法将数组作为参数以及int值k（顺序统计量，即数组中的第k个最小元素）。在这种情况下，k的值只是N/2，其中N是阵列长度。

实施是有点棘手得到正确的，但这里是它依赖Comparable<T>接口和Collections.shuffle()没有任何外部依赖的例子。

public final class QuickSelectExample { 

    public static <T extends Comparable<? super T>> 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 extends Comparable<? super T>> 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 <T extends Comparable<? super T>> 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 <T extends Comparable<? super T>> boolean less(T x, T y) { 
     return x.compareTo(y) < 0; 
    } 

    private static <T extends Comparable<? super T>> 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)]   " // 

Answer 8

做，在一行像亲：

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

强制转换为double，如果你期望double等