Posted on by tzry

LeetCode 1365. How Many Numbers Are Smaller Than the Current Number

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

Return the answer in an array.

Example 1:

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation:
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1).
For nums[3]=2 there exist one smaller number than it (1).
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).
Example 2:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]
Example 3:

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

Constraints:

2 <= nums.length <= 500
0 <= nums[i] <= 100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* arr;
int cmpfunc (const void * a, const void * b) {
   return  arr[*(int*)a] - arr[*(int*)b ];
}

int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize){
    *returnSize=numsSize;
    int* index=(int*)malloc(sizeof(int)*numsSize);
    for(int i=0;i<numsSize;++i){
        index[i]=i;
    }
    arr=nums;
    qsort(index, numsSize, sizeof(int), cmpfunc);
    int* ret=(int*)malloc(sizeof(int)*numsSize);
    ret[index[0]]=0;
    for(int i=1;i<numsSize;++i){
        if( nums[index[i]] == nums[index[i-1]] ){
            ret[index[i]]=ret[index[i-1]];
        }
        else{
            ret[index[i]]=i;
        }
    }
    free(index);
    return ret;
}


8 Replies to “LeetCode 1365. How Many Numbers Are Smaller Than the Current Number”

  3. Hi there. I discovered your blog by way of Google whilst searching for a comparable subject, your website came up. It appears to be great. I have bookmarked it in my google bookmarks to come back then. Sheryl Jarrett Liddle

    Reply

  5. Hello! I just would love to give a big thumbs up for the great details you have right here on this article. I will certainly be coming back to your blog site for more soon. Dana Alvie Alf

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *