剑指offer-35、数组中的逆序对
<h2 id="题描述">题⽬描述</h2><p>在数组中的两个数字，如果前⾯⼀个数字⼤于后⾯的数字，则这两个数字组成⼀个逆序对。输⼊⼀个数组，求出这个数组中的逆序对的总数。</p>
<p>输⼊⼀个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007</p>
<p>示例 1:<br>
输⼊: <br>
输出: 5<br>
限制：0 <= 数组⻓度 <= 50000</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴破解">暴⼒破解</h3>
<p>⾸先，也就是数组中任意两个数，只要前⾯的数⼤于后⾯的数，就是逆序对。先来⼀次暴⼒破解：遍历任意两个数，只要符合条件，总数就增加1。</p>
<pre><code class="language-java">class Solution {
public int reversePairs(int[] nums) {
int i=0, j=0, sum=0;
for( i=0; i<nums.length; i++ ){
for( j=i+1; j<nums.length; j++ ){
if( nums < nums ) sum++;
}
}
return sum;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²) - 对于每个元素，都需要与后续所有元素比较</li>
<li><strong>空间复杂度</strong>：O(1) - 只使用常数级别额外空间</li>
</ul>
<h3 id="归并排序法推荐">归并排序法（推荐）</h3>
<p>在归并排序的基础上稍微改动即可。以数组为例：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201649307.png" alt="" loading="lazy"></p>
<p>我们可以发现，其实在合并的过程中，两个有序的数组，可以直接计算出逆序数组的个数。我们以 ，实际上分为 和 ，逆序的个数为第⼀部分 中的逆序个数+第⼆部分 中的逆序个数，还有第三部分是 中的元素相对 的逆序个数。</p>
<p>分为两半之后的逆序个数，⼀看就是分治法，递归即可，⽽两部分的相对逆序，我们可以在合并有序数组的时候得出。</p>
<p>合并的时候使⽤双指针， i 指向第⼀个数组的第⼀个元素，j指向第⼆个数组的第⼀个元素。哪⼀个元素⼩，就将该元素写⼊新的数组中，同时指针后移。</p>
<p>如果第⼆个数组中的元素⼩于第⼀个数组中的元素，那么就构成了逆序对，逆序对的个数：如果中间分隔是索引是 mid ，那么构成逆序对的个数为 mid-i+1 。</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201650371.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201650505.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201650530.png" alt="" loading="lazy"></p>
<p><strong>核心原理：</strong>当左子数组的当前元素 <code>temp</code>大于右子数组的当前元素 <code>temp</code>时，左子数组中从 <code>i</code>到 <code>mid</code>的所有元素都与 <code>temp</code>构成逆序对，因为左右子数组都是有序的</p>
<pre><code class="language-java">public class Solution35 {
public static void main(String[] args) {
int[] nums = {8, 6, 4, 2, 7, 5, 3, 1};
Solution35 solution35 = new Solution35();
int result = solution35.InversePairs(nums);
System.out.println(result);
}
public int InversePairs(int[] array) {
if (array == null || array.length < 2) {
return 0;
}
int[] nums = new int;
return getNums(array, nums, 0, array.length - 1) % 1000000007;
}
public int getNums(int[] array, int[] nums, int left, int right) {
if (left >= right) {
return 0;
}
int mid = left + (right - left) / 2;
int leftNum = getNums(array, nums, left, mid) % 1000000007;
int rightNum = getNums(array, nums, mid + 1, right) % 1000000007;
return leftNum + rightNum + mergeNum(array, nums, left, mid, right);
}
public int mergeNum(int[] array, int[] nums, int left, int mid, int right) {
for (int i = left; i <= right; i++) {
nums = array;
}
int count = 0;
int i = left, j = mid + 1;
for (int k = left; k <= right; k++) {
if (i == mid + 1) {
array = nums;
j++;
} else if (j == right + 1) {
array = nums;
i++;
} else if (nums <= nums) {
array = nums;
i++;
} else {
array = nums;
j++;
count = (count + (mid - i + 1)) % 1000000007;
}
}
return count % 1000000007;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n log n) - 与归并排序相同</li>
<li><strong>空间复杂度</strong>：O(n) - 需要临时数组存储</li>
</ul>
<p>有⼀个很坑的地⽅：只要涉及到加和的地⽅都有可能溢出，⼀旦溢出就会导致结果出错，数据量⼤，很难调试。所以凡是涉及到加和的地⽅都要 % 1000000007 。</p>
<h3 id="树状数组法">树状数组法</h3>
<p>利用树状数组（Fenwick Tree）和离散化技术统计逆序对</p>
<pre><code class="language-java">import java.util.*;
public class Solution {
private int mod = 1000000007;
public int InversePairs(int[] nums) {
if (nums == null || nums.length == 0) return 0;
// 离散化处理：将原数组映射到紧凑的整数范围
int[] sorted = nums.clone();
Arrays.sort(sorted);
// 创建映射：原数组值 -> 离散化后的索引（从1开始）
Map<Integer, Integer> mapping = new HashMap<>();
int index = 1;
for (int num : sorted) {
if (!mapping.containsKey(num)) {
mapping.put(num, index++);
}
}
// 使用树状数组统计逆序对
FenwickTree tree = new FenwickTree(index - 1);
int count = 0;
// 从右向左遍历，统计每个元素左边比它小的元素数量
for (int i = nums.length - 1; i >= 0; i--) {
int pos = mapping.get(nums);
count = (count + tree.query(pos - 1)) % mod; // 查询比当前元素小的数量
tree.update(pos, 1); // 更新树状数组
}
return count;
}
// 树状数组实现
class FenwickTree {
private int[] tree;
private int n;
public FenwickTree(int size) {
this.n = size;
this.tree = new int;
}
// 低位操作
private int lowBit(int x) {
return x & (-x);
}
// 更新操作：在位置x增加value
public void update(int x, int value) {
while (x <= n) {
tree = (tree + value) % mod;
x += lowBit(x);
}
}
// 查询操作：求前x项的和
public int query(int x) {
int sum = 0;
while (x > 0) {
sum = (sum + tree) % mod;
x -= lowBit(x);
}
return sum;
}
}
}
</code></pre>
<ul>
<li><strong>间复杂度</strong>：O(n log n) - 离散化O(n log n)，树状数组操作O(log n)</li>
<li><strong>空间复杂度</strong>：O(n) - 树状数组和映射表空间</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19137145
頁:
[1]