苏州网站建设制作公司,景区网站建设的目标定位,怎么做非法网站,小鸟云服务器官网牛客网: BM20
题目: 求出数组中逆序对总数
思路: 使用归并排序思路#xff0c;先分裂#xff0c;再合并#xff0c;合并的时候#xff0c;左半段有序#xff0c;右半段有序#xff0c;如果左半段某个值大于右半段某个值 data[i] data[j]#xff0c; 则可通过j与右…牛客网: BM20
题目: 求出数组中逆序对总数
思路: 使用归并排序思路先分裂再合并合并的时候左半段有序右半段有序如果左半段某个值大于右半段某个值 data[i] data[j] 则可通过j与右半段起始坐标之间的距离算出共有多少个比data[i]小即这一小段的逆序对的数量在复制数组dataCopy中一直按照比较的结果来更新数值作为回溯时的data使用。
注意: 中间点 mid (leftright)/2需要归到左半段中否则递归时使用inverse(left, mid-1), 即下一层rightmid-1, 存在right left情况如果这样的话则需要在递归前添加判断单独处理否则会栈溢出。
代码:
package main
// import fmt/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param nums int整型一维数组 * return int整型
*/
const BASE 1000000007func InversePairsCount(data, dataCopy []int, left, right int) int {if left right {mid : left (right - left) 1leftCount : InversePairsCount(dataCopy, data, left, mid)rightCount : InversePairsCount(dataCopy, data, mid1, right)count : 0i : midj : rightidx : rightfor i left j mid {if data[i] data[j] {count j - middataCopy[idx] data[i]idx--i--} else {dataCopy[idx] data[j]idx--j--}}for i left {dataCopy[idx] data[i]idx--i--}for j mid {dataCopy[idx] data[j]idx--j--}return (count leftCount rightCount) % BASE} else{dataCopy[left] data[left]return 0}
}func InversePairs( nums []int ) int {// write code hereif len(nums) 0 {return 0}dataCopy : make([]int, len(nums))for i : 0; i len(nums); i {dataCopy[i] nums[i]}left, right : 0, len(nums) - 1count : InversePairsCount(nums, dataCopy, left, right)return count % BASE
}
