我想知道是否可能找到一个数组的中位数？例如，假设我有一个大小为九的数组。是否可以找到这个数组的中间插槽？
9个回答
26
假设数组 x 是有序的且长度为 n：
如果n为奇数，则中位数为 x[(n-1)/2]。
如果n为偶数，则中位数为 ( x[n/2] + x[(n/2)-1] ) / 2。
- Turtle
3
这将至少需要O(nlogn)的时间。 - darkknight444
这实际上将需要恒定的时间。 - Node.JS
@Node.JS 如果列表已排序，则时间复杂度为常数级。如果列表尚未排序，则时间复杂度为nlogn。如果您想在所有情况下都达到最佳状态，该函数可以要求用户传递一个布尔值，以指示列表是否已排序。 - aeskreis
8
如果您想使用任何外部库，可以使用Apache commons math library，通过它您可以计算中位数。
如需更多方法和用法，请查看API文档。
如需更多方法和用法，请查看API文档。
import org.apache.commons.math3.*;
.....
......
........
//calculate median
public double getMedian(double[] values){
Median median = new Median();
double medianValue = median.evaluate(values);
return medianValue;
}
.......
- 如需了解更多有关evaluate方法的信息，请访问AbstractUnivariateStatistic#evaluate
在程序中计算
通常，中位数是使用以下两个公式计算的，具体请参见此处
如果n为奇数，则中位数（M）=第((n + 1)/2)项的值。
如果n为偶数，则中位数（M）= [((n)/2)th item term + ((n)/2 + 1)th item term ]/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;
- Aniket Kulkarni
2
在C++中，您可以使用std::nth_element函数；请参见http://cplusplus.com/reference/algorithm/nth_element/。
- Oliver Charlesworth
2
在Java中：
int middleSlot = youArray.length/2;
yourArray[middleSlot];
或者
yourArray[yourArray.length/2];
一行代码实现。
这是因为在Java中，数组的大小是固定的。
注意：3/2 == 1
资源：
- Colin Hebert
4
1你的答案是错误的。例如，考虑一个有两个元素的数组：3和75。你的答案将中位数给出为75。 - Turtle
3{3, 75} 的中位数是多少？ - Wouter Lievens
1梅森，你似乎把中位数和平均数搞混了。 - Gal
4根据中位数的定义，如果数值数量为偶数，中位数就是中间两个数的平均值。所以曼森是正确的。 - Chris Li
1
像专业人士一样在一行中完成：
return (arr[size/2] + arr[(size-1)/2]) / 2;
如果您期望得到一个双精度浮点数，请将其转换为
double等。- i_use_the_internet
1
这当然假定列表已经排序。 - aeskreis
1
vector<int> v;
size_t len = v.size;
nth_element( v.begin(), v.begin()+len/2,v.end() );
int median = v[len/2];
- Kirill V. Lyadvinsky
0
上面的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];);
}
请注意，这只是概念验证和即兴操作。如果您认为可以使它更紧凑或不那么密集，请随意进行修改。请不要批评它。
- Matthew
0
还有另一种选择 - 通常，这里的建议要么是对数组进行排序，然后从这样的数组中取中位数，要么依赖于（外部）库解决方案。目前最快的排序算法是线性对数级别的，但是为了计算中位数，可能会做得更好。
从未排序的数组中计算中位数的最快算法是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)] " //
- quantum
0
在Java中，除以2.0就足以将int类型转换为double类型。
return n%2 == 0 ? (all[n/2] + all[n/2-1])/2.0 : all[(n-1)/2];
第一个条件检查值是否为偶数。
- torina
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接