携程笔试：第90百分数

题目描述：

思路：

知乎上的讨论

刚开始没读懂题，网上搜了一下关于第95百分位的解释，大家各有说法，各有自己的理解。但是看了很多人的评论也是，表示基本都看不懂。

从维基百科上可以找到这么一段话：

There is no standard definition of percentile, 
however all definitions yield similar results when the number of 
observations is very large and the probability 
distribution is continuous

可见对于百分位并没有十分标准的定义。所以仅在此简单总结一下第xth百分位的计算，以便日后查看，也希望大家能少走弯路，至于具体含义大家可以去维基百科查看。

既然网上没找到实现代码，就想到了Excel可能有相应的函数，果不其然。

res = PERCENTILE(array,p)

其中：array为你的序列存储位置，比如A1:A12(在excel里的位置对应题目测试样例的array[0:11]),p为百分位值（以题目为例，p=0.9）

然后查了下它的实现原理：

首先将你的输入数组进行从小到大排序，然后计算:

(n-1)*p = i + j

其中n为数组元素的个数，将计算结果的整数部分用i表示，小数部分用j来表示。则最终的percentile值为：

res = (1-j) array[i] + j array[i+1]

所以，题目给的数组是排好序的，所以我们计算（n-1）p = (12-1)0.9 = 9.9，则整数部分 i=9，小数部分j=0.9。查找数组得知，array[i] = array[9] = 7;array[i+1] = array[10] = 8。

因为，我们可以得到测试样例的结果为：

res = (1-j) array[i] + j array[i+1] =(1-0.9)7+0.98 = 7.9

代码实现：

import java.util.*;
public class Main {
    public static double getPercentile(int[] A, double p) {
        if (A == null)
            return 0;
        double res = 0;
        Arrays.sort(A);// 从小到大排序
        double x = (A.length - 1) * p;
        int i = (int) x;// 取出整数部分
        double j = x - i;// 还没找到最精确的取double数的小数部分的方法，有可能会有误差
        res = (1 - j) * A[i] + j * A[i + 1];
        return res;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        double p = 0.9;
        double res;
        int[] A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = in.nextInt();
        }
        res = getPercentile(A, p);
        System.out.println(res);
    }
}