如何统计数组中比当前元素小的所有元素数量?
数组中元素值都在100以内,数据量不限.
这种数据量大,数据范围不大的统计情况,是非常适合桶排序的.
桶排序并不是一个具体的排序,而是一个逻辑概念....之所以被叫做桶,是因为根据数据状况将每个索引值看做为一个容器,也就是相当于一个桶; 在遍历数据的时候将根据需要将数据放入每个桶中,遍历结束后将桶依次倒出....在桶内部,数据会根据需要处理成有序结构或者做计数.
我们再回到问题本身,既然要统计比自己小的数字数量,就需要统计每个数字的总个数,在对统计求和.
为了方便理解将数据范围缩小到10以内,数量也减少些....统计小于等于当前元素的值: bucket[i] = bucket[i] + bucket[i-1]
最后每个元素对应小于自己的元素个数为当前桶中元素对应的前一值,
即bucket[array[i] -...) {
int[] result = new int[array.length];
int[] bucket = new int[k + 1];
// 计数