题解 | 计算数组的小和

package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)
	arr := make([]int, n)
	for i := range arr {
		fmt.Scan(&arr[i])
	}
	res:= mergeAndCal(arr,0,len(arr)-1)
	fmt.Println(res)
}

//[]
func mergeAndCal(arr []int, l int, r int) int {
	if l == r {
		return 0
	}
	mid := (r-l)>>1 + l
	lCnt := mergeAndCal(arr, l, mid)
	rCnt := mergeAndCal(arr, mid+1, r)
	help := make([]int, r-l+1)
	i := l
	j := mid + 1
	idx := 0
	res := 0
	for i <= mid && j <= r {
		if arr[i] <= arr[j] {
			help[idx] = arr[i]
			res += (r - j + 1) * arr[i]
			i++
		} else {
			help[idx] = arr[j]
			j++
		}
		idx++
	}
	for i <= mid {
		help[idx] = arr[i]
		idx++
		i++
	}
	for j <= r {
		help[idx] = arr[j]
		idx++
		j++
	}
	for i := range help {
		arr[i+l] = help[i]
	}
	return res + lCnt + rCnt
}

func divideArray(nums []int, k int) [][]int {
	sort.Ints(nums)
	n := len(nums)
	res := [][]int{}
	for i := 0; i < n; i += 3 {
		if nums[i]+k > nums[i+2] {
			return [][]int{}
		} else {
			temp := []int{nums[i], nums[i+1], nums[i+2]}
			res = append(res, temp)
		}
	}
	return res
}

详细解答见bili，左程云P22算法讲解。使用help数组辅助排序。line35，arr[i]<arr[j]，那么比i大的元素个数为从j索引到r索引的元素个数。[0,mid]中已经实现过排序，所以需要算[mid+1,r]中有多少个元素大于arr[i]