algo/di-yi-zhan-da78c/shou-ba-sh-66994/gui-bing-p-1387f/

[giscus[bot]]

algo/di-yi-zhan-da78c/shou-ba-sh-66994/gui-bing-p-1387f/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！第 21 期打卡挑战 (https://opedk.xet.tech/s/4ptSo2) 开始报名！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下...

https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-66994/gui-bing-p-1387f/

[budiQaQ]

区间和的个数把老师的算法用cpp写完还是超时了..

[shiboys]

如果不是专业研究算法的，在归并排序中夹带私活并利用归并的特点，一般人真的很难想到，怪不得难度登记都是困难

[lemonzeng]

tnl

[marypeng1020]

看不懂这里： int start = mid + 1, end = mid + 1;

[shixinlu0730]

315 题的golang答案 好像不是golang语言。烦请更正一下。。

[shixinlu0730]

type Pair struct {
val, id int
}

func countSmaller(nums []int) []int {
n := len(nums)
count := make([]int, n)
temp := make([]Pair, n)
arr := make([]Pair, n)
for i, num := range nums {
arr[i] = Pair{val: num, id: i}
}

sortAndCount(arr, 0, n-1, temp, count)
return count

}

func sortAndCount(arr []Pair, lo, hi int, temp []Pair, count []int) {
if lo == hi {
return
}
mid := lo + (hi-lo)/2
sortAndCount(arr, lo, mid, temp, count)
sortAndCount(arr, mid+1, hi, temp, count)
merge(arr, lo, mid, hi, temp, count)
}

func merge(arr []Pair, lo, mid, hi int, temp []Pair, count []int) {
copy(temp[lo:hi+1], arr[lo:hi+1])

i, j := lo, mid+1
for p := lo; p <= hi; p++ {
	if i == mid+1 {
		arr[p] = temp[j]
		j++
	} else if j == hi+1 {
		arr[p] = temp[i]
		count[temp[i].id] += j - mid - 1
		i++
	} else if temp[i].val > temp[j].val {
		arr[p] = temp[j]
		j++
	} else {
		arr[p] = temp[i]
		count[temp[i].id] += j - mid - 1
		i++
	}
}

}

这是我重新用gpt生成的 应该没有问题

[codezs09]

merge应该可以原地进行的吧？不需要借用新数组
双指针 left 指向左区间，right 指向右区间，比较 left 和 right 元素的值。
如果 left <= right， 则 left++； 否则对调 left 和 right 指向的元素，调换后小的元素已经到了 left 的位置，然后仍然是 left++, right 不动。 这样的话额外空间占用为 O(1)

merge(int[] nums, int lo, int mid, int hi) {
   int left = lo, right = mid+1; 
   while (left <= mid) {
       if (nums[left] > nums[right]) {
            int tmp = nums[left]; 
            nums[left]= nums[right]; 
            nums[left] = tmp;
        } 
        left++; 
   }
}

[codezs09]

Never mind. 想岔了。交换后right 可能就不是有序的了。 所以此法不可行。