如何统计数组中比当前元素小的所有元素数量?
数组中元素值都在100以内,数据量不限.
这种数据量大,数据范围不大的统计情况,是非常适合桶排序的.
桶排序并不是一个具体的排序,而是一个逻辑概念....在桶内部,数据会根据需要处理成有序结构或者做计数.
我们再回到问题本身,既然要统计比自己小的数字数量,就需要统计每个数字的总个数,在对统计求和.
为了方便理解将数据范围缩小到10以内,数量也减少些....数组array={8, 1, 2, 2, 3}
1. 数据范围是10以内,那需要开辟0-11区间的11个桶进行统计,源数组与桶的对应方式如下:
2. 将原数组遍历统计后,放入数组.
3....统计小于等于当前元素的值: bucket[i] = bucket[i] + bucket[i-1]
最后每个元素对应小于自己的元素个数为当前桶中元素对应的前一值,
即bucket[array[i] -...) {
int[] result = new int[array.length];
int[] bucket = new int[k + 1];
// 计数