【题目】数组中有多少个小于当前数字的数字

1365. 有多少小于当前数字的数字
题目描述：给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。

总结三种解题方法。

方法1：双层for循环暴力寻找。

int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
     int *ret = (int *)calloc(numsSize, sizeof(int));
     int i, j;

     for (i = 0; i < numsSize; i++) {
         for(j = 0; j < numsSize; j++) {
             if (i != j && nums[j] < nums[i]) {
                 ret[i]++;
             }
         }
     }

     return ret;
}

方法2：构造二维数组（n维 x 2列），一列记录索引，一列记录索引值，然后重新排序。

int Cmp(const void *a, const void *b) // 索引值从小到大排序
{
    int *t1 = (int *)a;
    int *t2 = (int *)b;
    return t1[0] - t2[0];
}

int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize){
    int temp[numsSize][2]; // 每一行，一个记录索引，一个记录索引值
    memset(temp, 0, sizeof(temp));
    *returnSize = numsSize;
    int *res = calloc(numsSize, sizeof(int));

    for (int i = 0; i < numsSize; i++) { //记录索引和索引值
        temp[i][0] = nums[i];
        temp[i][1] = i;
    }

    qsort(temp, numsSize, sizeof(temp[0]), Cmp);

    // 此时，temp中按照索引值排好了序
    int currIndex = temp[0][1]; // 首先取最小值索引
    res[currIndex] = 0; // 没有比最小值更小的了，res[最小值] 为0.
    int currValue = 1;
    for (int i = 1; i < numsSize; i++) {
        if (temp[i][0] == temp[i - 1][0]) {
            res[temp[i][1]] = res[temp[i - 1][1]];
            currValue++; // 计数，每次递增
            continue;
        }
        res[temp[i][1]] = currValue++;
    }

    return res;
}

方法3：巧妙，计数排序，建立频次数组。频次数组怎么理解？频次，即某个数出现的次数。

int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    int *res = calloc(numsSize, sizeof(int));
    
    int record[101] = { 0 }; // 记录某个num出现的次数。
    for (int i = 0; i < numsSize; i++) {
        record[nums[i]]++;
    }

    // 构建频次数组
    for (int i = 1; i < 101; i++) {
        record[i] += record[i - 1];
    }

    for (int i = 0; i < numsSize; i++) { // 妙啊，对于数字i而言，record[i]表示数字i出现的频次，则record[i-1]表示小于它的数目总和
        if (nums[i] == 0) {
            res[i] = 0;
            continue;
        }

        res[i] = record[nums[i] - 1];
    }

    return res;
}

yo peace！