1365 有多少小于当前数字的数字

简单 计数排序

算法思路

非常显然的计数排序，无需多言。

代码实现

how-many-numbers-are-smaller-than-the-current-number.c

int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize) {
    returnSize[0] = numsSize;
    int* ret = (int*)malloc(numsSize * sizeof(int));
    int count[105], sum[105];
    memset(count, 0, 105 * sizeof(int));
    memset(sum, 0, 105 * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        count[nums[i]]++;
    }
    for (int i = 1; i <= 100; i++) {
        sum[i] = sum[i - 1] + count[i - 1];
    }
    for (int i = 0; i < numsSize; i++) {
        ret[i] = sum[nums[i]];
    }
    return ret;
}