四方位数
一个有序数组的四分位数就是三个点,将这个有序数组分成4个相等的部分. 这三个四分位数定义如下:
Q1: 第一个四分位数是有序数组中最小的数和中位数之间的中间数.
Q2: 第二个四分位数是有序数组中的中位数.
Q3: 第一个四分位数是有序数组中中位数和最大的数之间的中间数.
计算第一和第三个四分位数
我们采用维基上所说的第一种方式:
我们首先把有序数组分成两部分, 小的一半和大的一半;
如果有序数组的元素个数是奇数, 那么不要把中位数(有序数组的中间元素)放在两部分中任何一部分中.
如果有序数组中有偶数个元素, 将其平分成正好两半.
小的一半的中位数的值就是第一个四分位数, 第三个四分位数就是大的一半的中位数.
例子1
我们以下列有序数组为例:
6, 7, 15, 36, 39, 40, 41, 42, 43, 47, 49
其中中位数是40, 因为数组长度是奇数(11个), 我们不把中位数包含在那两半中:
小的一半:6, 7, 15, 36, 39
大的一半:41, 42, 43, 47, 49
小的一半的中位数是15,则第一个四分位数的值是15, 大的一半的中位数是43, 则第三个四分位数是43.
例子2
我们以下列有序数组为例:
7, 15, 36, 39, 40, 41
当有序数组的长度是偶数个时,我们把数组从中间平分:
小的一半:7, 15, 36
大的一半:39, 40, 41
小的一半的中位数是15,则第一个四分位数是15,而大的一半的中位数是40,则第三个四分位数就是40, 第二个四分位数是整个数组的中位数, 则是(36 + 39) / 2 = 37.5
问题:
给一个有n个元素的数组X, 求出第一个四分位数(Q1),第二个四分位数(Q2)和第三个四分位数(Q3). 可以肯定(Q1),(Q2)和(Q3)是整数.
输入格式:
第一行,一个整数N,表示后面输入数组的元素个数
第二行, 包含了N个整数x的数组, 用逗号分隔
其中 5 <= N <= 50
对每个整数xi, 有0 < xi <= 100
输出格式:
按以下顺序输出3行
- 第一行是Q1的值.
- 第一行是Q2的值.
- 第一行是Q3的值.
例子的输入:
9
3 7 8 5 12 14 21 13 18
例子的输出:
6
12
16
解释:
X = {3, 7, 8, 5, 12, 14, 21, 13, 18}, 当我们先按升序把元素排序, 就得到X = {3, 5, 7, 8, 12, 13, 14, 18, 21}, 显然X的中位数是12.
因为数组的长度是奇数, 我们排除中位数, 并平分数组:
小的一半(L): 3, 5, 7, 8
大的一半(U): 13, 14, 18, 21
然后,我们求得四分位数
- Q1是L的中位数,Q1 = (5 +７）/ 2 = 6
- Q2是X的中位数,Q2 = 12
- Q3是U的中位数,Q3 = (14 +18）/ 2 = 16
scala
object Solution {
def medianOfSorted(sorted: Array[Int]): Float = {
if (sorted.isEmpty) return Float.NaN
val mid: Int = sorted.length / 2
return if (sorted.length % 2 == 1) sorted(mid).toFloat else (sorted(mid - 1) + sorted(mid)) / 2f
}
def main(args: Array[String]) {
import java.util.Scanner
val scan: Scanner = new Scanner(System.in)
try {
val n: Int = scan.nextInt
scan.nextLine
val X: Array[Int] = scan.nextLine().split(" ").map(_.toInt).toArray
val sorted: Array[Int] = X.sorted
println("%.0f".format(medianOfSorted(sorted.slice(0, n / 2))))
println("%.0f".format(medianOfSorted(sorted)))
println("%.0f".format(medianOfSorted(sorted.slice(n / 2 + (n % 2), n))))
} finally {
scan.close()
}
}
}
python
def quartiles():
def median_sorted(_sorted):
_len = len(_sorted)
if _len == 0:
return None
mid = int(_len / 2)
return (_sorted[mid] + _sorted[mid - 1 + _len % 2]) / 2
n = int(input())
array = [int(s) for s in input().split(" ")]
_sorted = sorted(array)
print("{0:.0f}".format(median_sorted(_sorted[0: int(n / 2)])))
print("{0:.0f}".format(median_sorted(_sorted)))
print("{0:.0f}".format(median_sorted(_sorted[int(n / 2) + n % 2: n])))
if __name__ == '__main__':
quartiles()
java
import java.io.*;
import java.util.*;
import java.util.stream.Stream;
public class Solution {
static float medianOfSorted(int[] sorted) {
if (sorted.length == 0) return Float.NaN;
int mid = sorted.length / 2;
return (sorted[mid - 1 + (sorted.length % 2)] + sorted[mid]) / 2;
}
public static void main(String[] args) {
try (Scanner scan = new Scanner(System.in)) {
int n = scan.nextInt();
scan.nextLine();
int[] array = Stream.of(scan.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
Arrays.sort(array);
System.out.printf("%.0f\n", medianOfSorted(Arrays.copyOfRange(array, 0, n / 2)));
System.out.printf("%.0f\n", medianOfSorted(array));
System.out.printf("%.0f\n", medianOfSorted(Arrays.copyOfRange(array, n / 2 + n % 2, n)));
}
}
}
