c语言练习49：有多少⼩于当前数字的数字

有多少⼩于当前数字的数字

给你⼀个数组  nums ，对于其中每个元素 nums[i] ，请你统计数组中⽐它⼩的所有数字的数⽬。
换⽽⾔之，对于每个  nums[i] 你必须计算出有效的 j  的数量，其中 j 满⾜  j != i。

且nums[j] < nums[i] 。
排序，⼆分查找

• 算法流程： 1. 定义⼀个新数组 order ，将原数组中的所有数按照下标分别赋值给order数组并将order数组排 序（给出冒泡排序代码）；

2. 定义⼀个新数组 ans ⽤来记录数组中⼩于当前元素的个数；

3. 遍历原数组，利⽤⼆分查找算法将当前元素在 order 数组中的下标赋值给 ans 数组；

4. 更新数组⻓度并返回数组。

• ⼆分查找：

1. 定义两个变量 l 和 r ，分别作为查找的左边和右边界；

2. 定义⼀个变量 mid ，并将其初始化为 l 和 r 的中点；

3. 将 order 数组中下标为 mid 的数与⽬标数进⾏⽐较，若⽬标数较⼤，则将 l 更新为 mid+1 ，否则将 r 更新为 mid 。

4. 当左边界 l ⼩于右边界 r 时重复2，3步骤。

5. 返回左右其中⼀个边界值。

#include
//利⽤⼆分查找寻找第⼀次出现u时的下标，order为有序数组，orderSize为有序数组⻓度，u为需要查找的数
int low(int* order, int orderSize, int u) {
	//定义左右两边界，l为最左边，r为最右边
	int l = 0;
	int r = orderSize - 1;
	while (l < r) {
		//mid为l和r的中点，向下取整
		int mid = (l + r) / 2;
		//如果在有序数组中下标为中点的数⼩于要查找的数，则要查找的数⼀定在中点右边，将左边界修改为中点加1
		if (order[mid] < u) {
			l = mid+1;
		}
		else
			//否则在中点处或者中点左边部分，将右边界修改为中点，
			r = mid;
	}
	//当查找完成时l=r，返回其中⼀个即可
	return l;
}
int* smallerNumbersThanCurren(int* nums, int numSize, int* returnSize) {
	//定义答案数组
	int* ans = malloc(numSize * sizeof(int));
	//定义有序数组
	int* order = malloc(numSize * sizeof(int));
	int i = 0; int j = 0;
	int tmp = 0;
	//将原数组中的数放⼊有序数组，之后进⾏排序
	for (i = 0; i < numSize; i++) {
		order[i] = nums[i];
	}
	//冒泡排序
	for (i = 0; i < numSize; i++) {
		for (j = 0; j < numSize - 1 - i; j++) {
			if (order[j] >order[ j + 1]) {
				tmp =order[ j ];
				order[j] = order[j + 1];
				order[j + 1] = tmp;
			}
		}
	}
	//更新答案数组
	for (i = 0; i < numSize; i++) {
		//将当前数在有序数组中的下标存⼊答案数组，order：有序数组，numsSize：数组⻓度，nums[i]为要查找的数
		ans[i] = low(order, numSize, nums[i]);
	}
	*returnSize = numSize;
	return ans;
}