剑指offer-数组中的逆序对

一、题意

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
样例：
输入：[7，5，6，4]
输出：5

二、思路一

顺序扫描整个数组。每扫描到一个数字的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成了一个逆序对。假设数组中含有n个数字。由于每个数字都要和O(n)个数字作比较，因此这个算法的时间复杂度是O(n^2)。

三、思路二

可以利用归并排序的思想，在排序过程中统计逆序对的个数。
一个排序好的数组逆序对数为0。所以从排序角度来看，我们只要将每一个逆序对转换为正序，最后数组则是有序的。问题转换为如何利用排序统计逆序数。将一个逆序变为正序，只需交换两者即可，如果仅仅这样统计交换次数是不够的。比如5432，对于(5，2)这对逆序数，交换(5，2)后，数组序列变为2435，这样会丢失中间(4，2)和(3，2)的逆序对。所以必须基于相邻元素来统计交换次数。那么基于交换相邻元素的排序算法有冒泡排序，插入排序和归并排序（两个子数组合并可看做2个相邻交换，只不过需要特殊处理）。
插入排序的复杂度为O(n^2)，归并排序可以达到O(nlogn)。

四、代码实现

>folded main.go

package main

import "fmt"

func InverseParis(nums []int) int {
	// 存储排序好的数组
	tmp := make([]int, len(nums))

	// 合并两个排序好的数组
	var merge func (start, mid, end int) int
	merge = func (start, mid, end int) int { // 匿名函数
		if start >= end {
			return 0
		}
		p1, p2 := mid, end
		k, count := 0, 0
		for p1 >= start && p2 >= mid+1 {
			// 第一个数组中的数字不大于第二个数组中的数字，则进行下一轮的比较
			if nums[p1] <= nums[p2] {
				tmp[k] = nums[p2]
				p2--
				k++
			} else {
				// 两个数组合并时已排好序，对于num[p1]而言，至少有(p2-mid)个逆序对
				tmp[k] = nums[p1]
				count += p2 - mid
				p1--
				k++	
			}
		}
		// p1指向的数字此时都不大于p2指向的数字
		for p1 >= start {
			tmp[k] = nums[p1]
			p1--
			k++
		}
		for p2 >= mid+1 {
			tmp[k] = nums[p2]
			p2--
			k++
		}
		for i := 0; i <= k-1; i++ {
			nums[end-i] = tmp[i]
		}

		return count
	}

	var sort func (start, end int) int
	sort = func (start, end int) int {
		count := 0
		if start < end {
			// 每次排序都从中间分割
			mid := (start+end)/2
			count += sort(start, mid)
			count += sort(mid+1, end)
			count += merge(start, mid, end)
		}
		return count
	}
	return sort(0, len(nums)-1)
}

func main() {
	test := []int{7, 5, 6, 4}
	pairs := InverseParis(test)
	fmt.Println("样例：")
	for i := 0; i < len(test); i++ {
		fmt.Println(test[i])
	}
	fmt.Printf("逆序对个数：%d", pairs)
}

// 输出如下：
样例：
4
5
6
7
逆序对个数：5
Process finished with exit code 0

参考链接：

1、[剑指offer] 数组中的逆序对
2、剑指Offer（三十五）：数组中的逆序对