Java 查找数组的中值？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3691940/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding the median value of an array?
提问by Steffan Harris
I was wondering if it was possible to find the median value of an array? For example, suppose I have an array of size nine. Would it possible to find the middle slot of this array?
我想知道是否有可能找到数组的中值？例如，假设我有一个大小为 9 的数组。有可能找到这个数组的中间槽吗？
采纳答案by Turtle
Assuming the array xis sorted and is of length n:
假设数组x已排序且长度为n：
If n is odd then the median is x[(n-1)/2].
If n is even than the median is ( x[n/2] + x[(n/2)-1] ) / 2.
如果 n 为奇数，则中位数为 x[(n-1)/2]。
如果 n 是偶数，则中位数是 ( x[n/2] + x[(n/2)-1] ) / 2。
回答by Kirill V. Lyadvinsky
vector<int> v;
size_t len = v.size;
nth_element( v.begin(), v.begin()+len/2,v.end() );
int median = v[len/2];
回答by Colin Hebert
In java :
在 Java 中：
int middleSlot = youArray.length/2;
yourArray[middleSlot];
or
或者
yourArray[yourArray.length/2];
in one line.
在一行中。
That's possible because in java arrays have a fixed size.
这是可能的，因为在 java 数组中有一个固定的大小。
Note :3/2 == 1
笔记 ：3/2 == 1
Resources :
资源 ：
回答by Oliver Charlesworth
In C++, you can use std::nth_element; see http://cplusplus.com/reference/algorithm/nth_element/.
在 C++ 中，您可以使用std::nth_element; 参见http://cplusplus.com/reference/algorithm/nth_element/。
回答by Matthew
The Java answer above only works if there are is an odd ammount of numbers here is the answer I got to the solution:
上面的 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];);
}
And note that this is a proof of concept and off the fly. If you think that you can make it more compact or less intensive, go right ahead. Please don't criticize it.
请注意，这是一个概念证明，并且是即时的。如果您认为可以使其更紧凑或更不密集，请继续。请不要批评它。
回答by Aniket Kulkarni
If you want to use any external library here is Apache commons math libraryusing you can calculate the Median.
For more methods and use take look at the API documentation
如果您想使用任何外部库，这里是Apache commons 数学库，您可以使用它来计算Median。
有关更多方法和使用，请查看API 文档
import org.apache.commons.math3.*;
.....
......
........
//calculate median
public double getMedian(double[] values){
Median median = new Median();
double medianValue = median.evaluate(values);
return medianValue;
}
.......
- For more on evaluate method AbstractUnivariateStatistic#evaluate
Calculate in program
在程序中计算
Generally, median is calculated using the following two formulas given here
通常，使用此处给出的以下两个公式计算中值
If n is odd then Median (M) = value of ((n + 1)/2)th item term.
If n is even then Median (M) = value of [((n)/2)th item term + ((n)/2 + 1)th item term ]/2
如果 n 是奇数，则中值 (M) = 第 ((n + 1)/2) 项项的值。
如果 n 是偶数，则中位数 (M) = [((n)/2)th item term + ((n)/2 + 1)th item term ]/2 的值
It is very easy as you have 9 elements (odd number).
Find the middle element of an array.
In your program you can declare array
这很容易，因为您有 9 个元素（奇数）。
找到数组的中间元素。
在您的程序中，您可以声明数组
//as you mentioned in question, you have array with 9 elements
int[] numArray = new int[9];
then you need to sort array using Arrays#sort
那么你需要使用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;
回答by quantum
There is another alternative - in general, the suggestions here either suggest sorting the array then taking the median from such an array or relying on a (external) library solution. Fastest sorting algorithms today are linearithmic, on average, but it is possible to do better than that for the purposes of median calculation.
还有另一种选择 - 一般来说，这里的建议要么建议对数组进行排序，然后从这样的数组中取中位数，要么依赖（外部）库解决方案。平均而言，当今最快的排序算法是线性的，但出于中值计算的目的，它可能比线性算法做得更好。
The quickest algorithm to compute median from an unsorted array is QuickSelect, which, on average, finds the median in time proportional to O(N). The algorithm takes array as argument, together with int value k(the order statistic, i.e. k-th smallest element in the array). The value of k, in this case, is simply N/2, where N is array length.
从未排序数组计算中值的最快算法是QuickSelect，平均而言，它可以找到与 O(N) 成比例的时间中值。该算法以数组作为参数，连同 int 值k（顺序统计量，即数组中的第 k 个最小元素）。的值k，在这种情况下，仅仅是N / 2，其中N是阵列的长度。
Implementation is little tricky to get right but here is an example which relies on Comparable<T>interface and Collections.shuffle()without any external dependencies.
正确实现并不难，但这里有一个示例，它依赖于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;
}
}
The code produces the following order statistics for these input arrays:
该代码为这些输入数组生成以下订单统计信息：
" 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)] " //
回答by i_use_the_internet
Do it in one line like a pro:
像专业人士一样在一行中完成：
return (arr[size/2] + arr[(size-1)/2]) / 2;
cast to a doubleif you're expecting a double, etc.
double如果您期待 adouble等，则转换为a 。
回答by torina
In the case of Java, dividing by 2.0is enough to cast intto double:
在 Java 的情况下，除以2.0足以强制转换int为double：
return n%2 == 0 ? (all[n/2] + all[n/2-1])/2.0 : all[(n-1)/2];
The first condition checks if the value is even.
第一个条件检查值是否为偶数。
