题目描述
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例：
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
提示：
0 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
算法
本题参考了官方解答，自己做的还是超时了。。。。好菜。。。。
主要就是利用归并排序，并且在将两个子序列归并成为一个更长序列的时候，计算右侧小于当前元素的个数。
- 进入递归，递归的入口是数组元素索引
0和lenth-1 - 如果某次的入参
begin==end，说明他们两个索引指向了同一个元素，那么就返回 - 如果入参
begin<end，那么就获取中间索引mid=(begin+end)/2，然后继续递归merge(begin,mid)merge(mid+1,end)- 当上面两个函数执行完毕以后，就开始归并两个子序列
- 如果右边的子序列的值更小，那么就将他加入结果序列
- 如果左边的子序列的值更小，那么就将他加入结果序列，并且将右边子序列已经排序进入结果序列的元素个数加入到左边的值对应比他小的个数中，作为“贡献”
- 值得一提的是，我们还定义了一个下标数组，他表示的是
nums中元素的下标，他随着nums中元素移动而移动，这样做的好处是方便我们快速将某个元素在某次归并中获取的“贡献”值加入到最终的结果值中。 - 可以这样理解，对于
nums中的靠左的元素，他最先和右边一个元素比较，可以获取“贡献”，这个元素和他一起作为左边序列的元素和长度为2的序列作比较，再次获得贡献，然后他们再一起作为左边的序列。。。因此，每个元素实际上和他左边的所有的元素都做过了比较的。
代码
- go
func countSmaller(nums []int) []int {
length := len(nums)
if length == 0 {
return []int{}
}
res := make([]int, length)
indexs := make([]int, length)
for i := 0; i < length; i++ {
indexs[i] = i
}
// 下面采用归并排序计算结果
mergeFunc(nums, 0, length-1, indexs, res)
return res
}
func mergeFunc(nums []int, begin, end int, indexs, res []int) {
if begin == end {
return
}
mid := (begin + end) / 2
mergeFunc(nums, begin, mid, indexs, res)
mergeFunc(nums, mid+1, end, indexs, res)
lBegin, rBegin := begin, mid+1
interNums := make([]int, end-begin+1)
interIndexs := make([]int, end-begin+1)
interI := 0
for lBegin <= mid || rBegin <= end {
if lBegin <= mid && rBegin <= end {
if nums[lBegin] > nums[rBegin] {
interNums[interI] = nums[rBegin]
interIndexs[interI] = indexs[rBegin]
rBegin++
} else {
interNums[interI] = nums[lBegin]
interIndexs[interI] = indexs[lBegin]
lBegin++
res[interIndexs[interI]] += rBegin - mid - 1
}
} else if lBegin <= mid && rBegin > end {
interNums[interI] = nums[lBegin]
interIndexs[interI] = indexs[lBegin]
lBegin++
res[interIndexs[interI]] += rBegin - mid - 1
} else {
interNums[interI] = nums[rBegin]
interIndexs[interI] = indexs[rBegin]
rBegin++
}
interI++
}
for i := 0; i < interI; i++ {
nums[begin+i] = interNums[i]
indexs[begin+i] = interIndexs[i]
}
return
}
- C++
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
if(nums.size()==0){
return vector<int>{};
}
vector<int> res(nums.size());
vector<int> indexs(nums.size());
for(int i=0;i<nums.size();i++){
indexs[i]=i;
}
mergeSort(nums,0,nums.size()-1,indexs,res);
return res;
}
private:
void mergeSort(vector<int> &nums,size_t begin,size_t end,vector<int> &indexs,vector<int> &res){
if(begin==end){
return;
}
size_t mid=(begin+end)/2;
mergeSort(nums,begin,mid,indexs,res);
mergeSort(nums,mid+1,end,indexs,res);
vector<int> interNums(end-begin+1);
vector<int> interIndexs(end-begin+1);
size_t lBegin=begin;
size_t rBegin=mid+1;
size_t interI=0;
while(lBegin<=mid||rBegin<=end){
if(lBegin<=mid&&rBegin<=end){
if(nums[lBegin]>nums[rBegin]){
interNums[interI]=nums[rBegin];
interIndexs[interI]=indexs[rBegin];
rBegin++;
}else{
interNums[interI]=nums[lBegin];
interIndexs[interI]=indexs[lBegin];
lBegin++;
res[interIndexs[interI]]+=rBegin-mid-1;
}
}else if(lBegin<=mid&&rBegin>end){
interNums[interI]=nums[lBegin];
interIndexs[interI]=indexs[lBegin];
lBegin++;
res[interIndexs[interI]]+=rBegin-mid-1;
}else{
interNums[interI]=nums[rBegin];
interIndexs[interI]=indexs[rBegin];
rBegin++;
}
interI++;
}
for(size_t i=0;i<interI;i++){
nums[begin+i]=interNums[i];
indexs[begin+i]=interIndexs[i];
}
return;
}
};