使用归并排序思想解决逆序对数量问题

本贴最后更新于 318 天前,其中的信息可能已经时过境迁

概述

归并排序算法,想必诸位都十分熟悉。其基本思想也就是分治。整个排序过程分成两部分--分治法将问题(divide)成一些小的问题然后递归求解,而**治(conquer)**的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之。

思路

拆分阶段

img

分的过程很容易看懂,即将一个大的数组拆分成若干个小的数组,减少问题规模。

合并阶段

img

img

实现

	public static void mergeSort(int [] arr) {
		int [] temp = new int [arr.length];
		//通过辅助数组可以有效的利用空间,减少空间复杂度。防止sort时递归创建多个数组,增加空间开销
		sort(arr, 0, arr.length - 1, temp);
	}
	/**对arr数组的[left...right]进行归并排序
	**/
	private static void sort(int [] arr, int left, int right, int [] temp) {
		//保证排序边界的有效性
		if(left < right) {
			int mid = (right + left) / 2;
			sort(arr, left, mid, temp);
			sort(arr, mid + 1, right, temp);
			merge(arr, left, mid, right, temp);
		}
	}
	//将[left...mid]和[mid+1...right]进行合并
	private static void merge(int [] arr, int left, int mid,int right, int [] temp) {
		int i = left; //指向左侧索引
		int j = mid +1; //指向右侧索引
		int t = 0; //指向temp数组的指针
		while(i <= mid && j <= right) {
			if (arr[i] <= arr[j]) {
				temp[t++] = arr[i++];
			} else {
				temp[t++] = arr[j++];
			}
		}
		//未被合并的数组元素直接放到后面
		while(i <= mid) temp[t++] = arr[i++];
		while(j <= right) temp[t++] = arr[j++];
		//将已经排序的temp数组中的元素复制到arr数组中
		t = 0;
		while(left <= right) arr[left++] = temp[t++];
	}

扩展与应用

剑指 Offer 51. 数组中的逆序对

image-20210315120121080

那么求逆序对和归并排序又有什么关系呢?关键就在于「归并」当中「并」的过程。我们通过一个实例来看看。

首先原始数组为 [2,3,5,7,1,4,6,8]。在合并时比较 i 所指向的元素 2 以及 j 所指向的元素 1 发现 1 <2 则将元素 1 放到第一个位置。进而我们发现 元素1 与前边 d 的 2,3,5,7 分别构成了逆序对。逆序数为 4

image-20210315133539297

然后 j 后移,发现 2<4,此时可以直接将 2 放到第二个位置,此时并未构成逆序对

image-20210315133612645

i 后移,发现 3<4,直接将 3 放到第三个位置,同样未构成逆序对。

image-20210315133712925

然后 i 继续后移,发现 4<5,将 4 放到第四个位置上,并且此时 4 和前边的 5,7 构成了逆序对。

image-20210315133736692

image-20210315133813899

分析到这里我们就可以发现一个规律,就是在合并时,当后一个数组索引 j 所指向的元素大于前一个数组索引 i 所指向的元素时,会构成逆序对,且逆序对的个数为前一个数组未被排序的元素个数即 mid - i +1 个。

重复做以上操作便可以得到下边的结果:

image-20210315135315747

代码实现

/**
使用归并排序思想来解决逆序对问题
**/
class Solution {
    public int reversePairs(int[] nums) {
        int [] temp = new int [nums.length];
        return split(nums, 0, nums.length - 1, temp);
    }
    /**
    计算num数组[left .. right]逆序对的个数
    **/
    private int split(int [] nums, int left, int right, int [] temp) {
        if(nums.length < 2) return 0;
        if(left < right) {
            int mid = (right - left) / 2 + left;
            int leftNum = split(nums, left, mid, temp);
            int rightNum = split(nums, mid + 1, right, temp);
            int mergeNum = merge(nums, left, mid, right, temp);
            return leftNum + rightNum + mergeNum;
        }
        return 0;
    }
    /**
    计算合并nums数组[left...mid]以及[mid+1 .. right]过程中产生的逆序对个数
    **/
    private int merge(int [] nums, int left, int mid, int right, int [] temp) {
        int res = 0;
        int i = left;
        int j = mid + 1;
        int t = 0; //指向临时数组的索引
        while(i <= mid && j <= right) {
            if(nums[j] < nums[i]) {
                res += mid - i + 1;
                temp[t++] = nums[j++];
            } else {
                temp[t++] = nums[i++];
            }
        }
        while(i <= mid) {
            temp[t++] = nums[i++];
        }
        while(j <= right) {
            temp[t++] = nums[j++];
        }
        //将已经排序好的数组元素复制到nums数组中
        t = 0;
        while(left <= right) {
            nums[left++] = temp[t++];
        }
        return res;
    }
}

总结

归并排序本质上一个分治思想的一种体现,通过将大问题进行拆分,分成若干小问题分别求解。然后将求解结果进行合并,得到一个最终解,进而解决该问题。

引用

  1. https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/shu-zu-zhong-de-ni-xu-dui-by-leetcode-solution/
  2. https://www.cnblogs.com/chengxiao/p/6194356.html
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3014 引用 • 8158 回帖 • 546 关注
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • 算法
    375 引用 • 252 回帖 • 20 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...