Hackrank 统计十日通(第一天) 四分位距

四分位距 Interquartile Range

一个数组的四分位距是第一个四分位数(Q₁)和第三个四分位数(Q₃)的差. (例如:(Q₃ - Q₁)

维基定义
四分位距(interquartile range), 是描述统计学中的一种方法, 以确定第三四分位数和第一四分位数的差, 和方差, 标准差一样, 表示统计资料中个变量的分散情况, 但四分位距更多为一种稳健统计

目标

给定一个含n个整数的数组X, 和一个数组F, 表示X中各个元素的出现频率. 通过这两个数组得到一个数据集S, X中元素x_i应该在S出现f_i次. 并计算和打印出S的四分位距, 精确到小数点后一位(例如:12.3)

提示

当一个数组有偶数个元素时,不要用整数相除来计算中间两个元素的平均值. 不要把中位数包含在数组大的一半和小的一半中.

输入格式

第一行输入一个整数n,表示数组X和F的元素数量.
第二行输入包含以空格分隔的n个整数,表示数组X的各个元素.
第三行输入包含以空格分隔的n个整数,表示数组F的各个元素.

约束条件

• 5 <= n <= 50
• 0 < x_i <= 100, x_i是X数组中第i个元素
• 0 < f_i的总和 <= 1000, -
• f_i是F数组中第i个元素
• S的元素个数等于F数组的元素之和

输出格式

构建数据集S,打印出它的四分位距, 精确到小数点后一位,(例如:12.3)

示例输入

6
6 12 8 10 20 16
5 4 3 2 1 5

示例输出

9.0

示例解析

元素	频率
6	5
12	4
8	3
10	2
20	1
16	5

首先, 根据数组X和对应的元素频率F,创建数据集S,得到:

S={6,6,6,6,6,8,8,8,10,10,12,12,12,12,16,16,16,16,16,20}

因为S中有偶数个元素, 我们将S平分为大小两半:

小的一半(L): 6, 6, 6, 6, 6, 8, 8, 8, 10, 10
大的一半 (U): 12, 12, 12, 12, 16, 16, 16, 16, 16, 20

然后,我们查找Q₁, 小的一半中有10个元素,那么Q₁就是中间两个元素(6和8)的平均值,即Q₁ = (6 + 8) / 2 = 7.0

然后,我们查找Q₃, 大的一半中也有10个元素, 那么Q₃就是中间两个元素(16和16)的平均值,即Q₃ = (16 + 16) / 2 = 16.0

最后,我们计算四分位距为Q₃ - Q₁ = 16.0 - 7.0 = 9.0, 打印9.0为我们的答案

python

from functools import reduce

def interquartile_range():
    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())
    X = [int(x) for x in input().split(" ")]
    F = [int(f) for f in input().split(" ")]
    S = sorted(reduce(lambda a, b: a + b, [[x] * f for x, f in zip(X, F)]))
    _len = len(S)
    print("{0:.1f}".format(median_sorted(S[int(_len / 2) + _len % 2: _len]) - median_sorted(S[0: int(_len / 2)])))


if __name__ == '__main__':
    interquartile_range()

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 F: Array[Int] = scan.nextLine().split(" ").map(_.toInt).toArray
            val S: Array[Int] = X.zipAll(F, 0, 0).map(x_f => Array.fill(x_f._2)(x_f._1)).flatten.sorted
            println("%.1f".format(medianOfSorted(S.takeRight(S.length / 2)) -  medianOfSorted(S.take(S.length / 2))))
        } finally {
            scan.close()
        }
    }
}

java

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;
import java.util.stream.Collectors;

public class Solution {
    static float medianOfSorted(int[] sorted) {
        if (sorted.length == 0) return Float.NaN;
        int mid = sorted.length / 2;
        return (sorted[mid - (sorted.length % 2 == 1 ? 0 : 1)] + sorted[mid]) / 2;
    }
    public static void main(String[] args) {
        try (Scanner scan = new Scanner(System.in)) {
            int n = scan.nextInt();
            scan.nextLine();
            int[] X = Stream.of(scan.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int[] F = Stream.of(scan.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int[] S = IntStream.range(0, n).mapToObj(i -> IntStream.range(0, F[i]).map(_i -> X[i])).collect(Collectors.<IntStream>reducing(IntStream::concat)).get().sorted().toArray();
            System.out.printf("%.1f\n", medianOfSorted(Arrays.copyOfRange(S, S.length - S.length / 2, S.length)) - medianOfSorted(Arrays.copyOfRange(S, 0, S.length / 2)));
        }
    }
}