Given a list of integers representing the lengths of urls, find the 95 percentile of all lengths (95% of the urls have lengths <= returned length).

Assumptions

• The maximum length of valid url is 4096

• The list is not null and is not empty and does not contain null

Examples

• [1, 2, 3, ..., 95, 96, 97, 98, 99, 100], 95 percentile of all lengths is 95.

Solution: 先bucket sort，再累加各bucket值，直到>= 95%。为了更快，可以从尾开始累加，直到>= 5%。注意i--和--i的不同导致结果相差1

  public int percentile95(List<Integer> lengths) {
    int[] bucket = new int[4097];
    int count_05 = (int)(lengths.size() * 0.05);
    int num = 0;
    for (int i : lengths) {
      bucket[i]++;
    }
    int length = 4097;
    while (num <= count_05) {
      num += bucket[--length];   //注意不能length--，否则得到的结果是< 95%
    }
    return length;
  }