LeetCode 315.计算右侧小于当前元素的个数_计算右侧 于当前元素的个数

力扣本题链接

思路：从最后一个开始，用二分法插入到一个新的数组，这样新数组就是有序的，那么此时该数字在新数组中的坐标就是原数组中其右边所有较小数字的个数。
核心代码请参考文章：【C语言刷LeetCode】315. 计算右侧小于当前元素的个数（H）

测试用例

输入： n = 4
nums = [7,9,6,2]
输出：[2,2,1,0]

解释：
7 的右侧有 2 个更小的元素 (6 和 2)
9 的右侧有 2个更小的元素 (6 和 2)
6 的右侧有 1 个更小的元素 (2)
2 的右侧有 0 个更小的元素

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// we have defined the necessary header files here FOR this problem.
// IF additional header files are needed IN your program, please IMPORT here.

void Insetone(int *temp, int num, int count,int right)
{
    int idx = count;
    while(idx > right)
    {
        temp[idx] = temp[idx -1];
        idx--;
    }
    temp[idx] = num;
}

int* countSmaller(int* nums, int numssize)
{
    int i;
    int *retarr;
    int *temp;
    int left = 0;
    int right;
    int mid;
    int count = 0;
    
    retarr = (int *)malloc(sizeof(int) * numssize);
    memset(retarr, 0, sizeof(int)* numssize);
    temp = (int *)malloc(sizeof(int) * numssize);
    memset(temp, 0, sizeof(int)* numssize);
    for(i = numssize -1; i >= 0; i--)
    {
        right = count;
        left = 0;
        
        while(left < right)
        {
            mid = (left + right) / 2;
            if(nums[i] <= temp[mid])
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        
        retarr[i] = right;
       Insetone(temp, nums[i], count, right);
        count++;
    }
    free(temp);
    return retarr;
    
    
}
int main()
{
    // please define the C input here. FOR EXAMPLE: int n; scanf("%d",&n);
    // please finish the FUNCTION body here.
    // please define the C output here. FOR EXAMPLE: printf("%d",a);
    int n;
    scanf("%d\n",&n);
    int *nums;
	nums = (int *)malloc(sizeof(int) * n);
    int *result;
	result = (int *)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &nums[i]);
    }
    result = countSmaller(nums, n);
    
    for(int i = 0; i < n; i++)
    {
    	if(i == n - 1)
    	{
    		printf("%d", result[i]);
		}
		else 
		{
			printf("%d ", result[i]);
		}
	}
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88