百度笔试题之数组差值（题目与源码） ********************************* 给定一个长度为n并且只含有非负整数的数组A，显然这个数组一共有n*(n+1)/2个区间（每个区间至少有一个元素）。给定m个查询值K，对于每个查询值K，我们将每个区间最小值与K做“差值”，“差值”的定义如下： 当最小值MINi不小于K时，则“差值”为MINi – K 否则“差值”为0 你的任务是求出对于每个查询值K时，n*(n+1)/2个“差值”的和。 【数据范围】 1 ≤ n, m ≤ 10
一个n个元素组成的集合中，第K个顺序统计量（Order Statistic）指的是该集合中第K小的元素，我们这里要讨论的是如何在线性时间（linear time）里找出一个数组的第K个顺序统计量。该问题的算法对于C++程序员来说有一定的借鉴价值。具体如下：
一、问题描述：
问题：给定一个含有n个元素的无序数组，找出第k小的元素。
k = 1 ：最小值
k = n ：最大值
k = ⌊(n+1)/2⌋ or ⌈(n+1)/2⌉ ：中位数
找最大值或最小值很简单，只需要遍历一次数组并记录下最大值或最
