死磕算法系列文章
- 干货 | 手撕十大经典排序算法
- 剑指offer | 认识面试
- 剑指offer | 面试题2：实现Singleton模式
- 剑指offer | 面试题3：二维数组的查找
- 剑指offer | 面试题4：替换空格
- 剑指offer | 面试题5：从尾到头打印链表
- 剑指offer | 面试题6：重建二叉树
- 剑指offer | 面试题7：用两个栈实现队列
- 剑指offer | 面试题8：旋转数组的最小数字
- 剑指offer | 面试题9：斐波那契数列
- 剑指offer | 面试题10：青蛙跳台阶问题
- 剑指offer | 面试题11：矩阵覆盖
- 剑指offer | 面试题12：二进制中1的个数
- 剑指offer | 面试题13：数值的整数次方
- 剑指offer | 面试题14：打印从1到最大的n位数
- 剑指offer | 面试题15：删除链表的节点
- 剑指offer | 面试题16：将数组中的奇数放在偶数前
- 剑指offer | 面试题17：链表中倒数第k个节点
- 剑指offer | 面试题18：反转链表
- 剑指offer | 面试题19：合并两个有序链表
- 剑指offer | 面试题20：判断二叉树A中是否包含子树B
- 剑指offer | 面试题21：二叉树的镜像
- 剑指offer | 面试题22：顺时针打印矩阵
- 剑指offer | 面试题23：包含min函数的栈
- 剑指offer | 面试题24：栈的压入、弹出序列
- 剑指offer | 面试题25：从上到下打印二叉树
- 剑指offer | 面试题26：二叉搜索树的后序遍历序列
- 剑指offer | 面试题27：二叉树中和为某一值的路径
- 剑指offer | 面试题28：复杂链表的复制
- 剑指offer | 面试题29：二叉搜索树转换为双向链表
- 剑指offer | 面试题30：字符串的排列
- 剑指offer | 面试题31：数组中出现次数超过一半的数字
- 剑指offer | 面试题32：最小的k个数
- 剑指offer | 面试题33：连续子数组的最大和
- 剑指offer | 面试题34：1～n 整数中 1 出现的次数
- 剑指offer | 面试题35：把数组排成最小的数
- 剑指offer | 面试题36：丑数
- 剑指offer | 面试题37：第一个只出现一次的字符
“Leetcode : https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof
“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_38_reversePairs/Solution.java
剑指 Offer 51. 数组中的逆序对
“题目描述 ：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 难度：困难
示例 1:
代码语言：javascript复制输入: [7,5,6,4]
输出: 5
方法1：暴力破解
使用两层 for 循环枚举所有的数对，逐一判断是否构成逆序关系。
/**
* 暴力破解
* @param nums
* @return
*/
public static int reversePairs1(int[] nums) {
int cnt = 0;
int len = nums.length;
for (int i = 0; i < len - 1; i ) {
for (int j = i 1; j < len; j ) {
if (nums[i] > nums[j]) {
cnt ;
}
}
}
return cnt;
}
复杂度分析：
- 时间复杂度：O(N^2) ，这里 N 是数组的长度；
- 空间复杂度：O(1) 。
方法二：归并排序
先归并，再统计逆序对的个数。
「归并排序」与「逆序对」是息息相关的。归并排序体现了 “分而治之” 的算法思想，具体为：
- 分：不断将数组从中点位置划分开(即二分法)， 将整个数组的排序问题转化为子数组的排序问题;
- 治：划分到子数组长度为1时，开始向上合并，不断将较短排序数组合并为较长排序数组，直至合 并至原数组时完成排序;
“如下图所示，为数组 [7, 3, 2, 6, 0, 1, 5, 4]的归并排序过程。
合并阶段 本质上是 合并两个排序数组 的过程，而每当遇到 左子数组当前元素 > 右子数组当前元素 时，意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」 。
“如下图所示，为左子数组 [2, 3, 6, 7] 与 右子数组 [0, 1, 4, 5] 的合并与逆序对统计过程。
思路流程：
merge_ sort() 归并排序与逆序对统计:
- 终止条件：当 l ≥ r 时，代表子数组长度为 1，此时终止划分;
- 递归划分：计算数组中点 m，递归划分左子数组merge_ sort(1, m)和右子数组merge_ sort(m 1,r) ;
- 合并与逆序对统计:
- 当i=m 1时：代表左子数组已合并完，因此添加右子数组当前元素tmp[i]，并执行 j=j 1;
- 否则，当j=r 1时:代表右子数组已合并完，因此添加左子数组当前元素tmp[i] ，并 执行i=i 1 ;
- 否则，当tmp[i]≤tmp[j]时:添加左子数组当前元素tmp[i]， 并执行i=i 1;
- 否则(即tmp[i]> tmp[j]) 时:添加右子数组当前元素tmp[j]，并执行j=j 1 ;此时 构成m-i 1个「逆序对」，统计添加至 res ;
- 暂存数组 nums 躯间 [i,r] 内的元素至辅助数组tmp ;
- 循环合并：设置双指针i, j分别指向左/子数组的首元素;
- 返回值:返回直至目前的逆序对总数res ; reversePairs() 主函数：
- 初始化：辅助数组tmp，盱合并阶段暂存元素;
- 返回值：执行归并排序merge_ sort() ， 并返回逆序对总数即可; 如下图所际，为数组[7, 3,2, 6, 0,1, 5, 4]的归并排序与逆序对统计过程。
复杂度分析:
- 时间复杂度O(NlogN) ：中N为数组长度;归并排序使用O(N log N)时间;
- 空间复杂度O(N) ：辅助数组tmp占用O(N)大小的额外空间;
代码：
代码语言：javascript复制package com.nateshao.sword_offer.topic_38_reversePairs;
/**
* @date Created by 邵桐杰 on 2021/12/14 20:45
* @微信公众号 程序员千羽
* @个人网站 www.nateshao.cn
* @博客 https://nateshao.gitee.io
* @GitHub https://github.com/nateshao
* @Gitee https://gitee.com/nateshao
* Description: 剑指 Offer 51. 数组中的逆序对
* 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
* 输入一个数组，求出这个数组中的逆序对的总数。
* <p>
* 思路：本质是归并排序，在比较时加入全局变量 count 进行记录逆序对的个数，若
* data[start] >= data[index] ，则 count 值为 mid 1-start
*/
public class Solution {
public static void main(String[] args) {
int[] arr = {7, 5, 6, 4};
System.out.println("reversePairs(arr) = " reversePairs(arr));//reversePairs(arr) = 5
System.out.println("reversePairs1(arr) = " reversePairs1(arr));
}
/**
* 暴力破解
*
* @param nums
* @return
* https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/bao-li-jie-fa-fen-zhi-si-xiang-shu-zhuang-shu-zu-b/
*/
public static int reversePairs1(int[] nums) {
int cnt = 0;
int len = nums.length;
for (int i = 0; i < len - 1; i ) {
for (int j = i 1; j < len; j ) {
if (nums[i] < nums[j]) {
cnt ;
}
}
}
return cnt;
}
/************** k神 **************/
int[] nums, tmp;
public int reversePairs2(int[] nums) {
this.nums = nums;
tmp = new int[nums.length];
return mergeSort(0, nums.length - 1);
}
private int mergeSort(int l, int r) {
// 终止条件
if (l >= r) return 0;
// 递归划分
int m = (l r) / 2;
int res = mergeSort(l, m) mergeSort(m 1, r);
// 合并阶段
int i = l, j = m 1;
for (int k = l; k <= r; k )
tmp[k] = nums[k];
for (int k = l; k <= r; k ) {
if (i == m 1)
nums[k] = tmp[j ];
else if (j == r 1 || tmp[i] <= tmp[j])
nums[k] = tmp[i ];
else {
nums[k] = tmp[j ];
res = m - i 1; // 统计逆序对
}
}
return res;
}
/************* 剑指offer *****************/
private static int count = 0;
public static int reversePairs(int[] array) {
if (array == null) return 0;
mergeSort(array, 0, array.length - 1);
return count;
}
private static void mergeSort(int[] data, int start, int end) {
int mid = (start end) / 2;
if (start < end) {
mergeSort(data, start, mid);
mergeSort(data, mid 1, end);
merge(data, start, mid, end);
}
}
private static void merge(int[] data, int start, int mid, int end) {
int arr[] = new int[end - start 1];
int c = 0;
int s = start;
int index = mid 1;
while (start <= mid && index <= end) {
if (data[start] < data[index]) {
arr[c ] = data[start ];
} else {
arr[c ] = data[index ];
count = mid 1 - start;
count %= 1000000007;
}
}
//把左边剩余的数移入数组
while (start <= mid) {
arr[c ] = data[start ];
}
//把右边剩余的数移入数组
while (index <= end) {
arr[c ] = data[index ];
}
//把新数组中的数覆盖nums数组
for (int d : arr) {
data[s ] = d;
}
}
}
https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/
