原创

【剑指Offer】035——数组中的逆序对(数组)

题目描述

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007(数据过大时,取余)
输入描述:
题目保证输入的数组中没有的相同的数字,数据范围:

对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
示例1

输入

1,2,3,4,5,6,7,0

输出

7

解题思路

很容易想到的方法就是遍历每一个元素,让其与后面的元素对比,如果大于则count++,但是这样的时间复杂度是$O(n^2)$,因此,我们可以用归并排序思路。
file

例如7,5,4,6可以划分为两段7,5和4,6两个子数组

  1. 在7,5中求出逆序对,因为7大于5所以有1对
  2. 在6,4中求出逆序对,因为6大于4所以逆序对再加1,为2
  3. 对7,5和6,4进行排序,结果为5,7,和4,6
  4. 设置两个指针分别指向两个子数组中的最大值,p1指向7,p2指向6
  5. 比较p1和p2指向的值,如果大于p2,因为p2指向的是最大值,所以第二个子数组中有几个元素就有几对逆序对(当前有两个元素,逆序对加2,2+2=4),7>6,比较完之后将p1指向的值放入辅助数组里,辅助数组里现在有一个数字7,然后将p1向前移动一位指向5
  6. 再次判断p1和p2指向的值,p1小于p2,因为p1指向的是第一个子数组中最大值,所以子数组中没有能和当前p2指向的6构成逆序对的数,将p2指向的值放入辅助数组,并向前移动一位指向4,此时辅助数组内为6,7
  7. 继续判断p1(指向5)和p2(指向4),5>4,第二个子数组中只有一个数字,逆序对加1,4+1=5,为5对,然后将5放入辅助数组,第一个子数组遍历完毕,只剩下第二个子数组,当前只有一个4,将4也放入辅助数组,函数结束。辅助数组此时为4,5,6,7.逆序对为5.

参考代码

Java

public class Solution {
    public int InversePairs(int [] array) {
        int len = array.length;
        if (array == null || len <= 0){
            return  0;
        }
        return mergeSort(array, 0, len - 1);
    }
    public int mergeSort(int[] array, int start, int end){
        // 递归结束标志
        if (start == end) return 0;
        int mid = start +  (end - start)/2;         // 数组分为两部分
        // 细分排序
        int left_count = mergeSort(array, start, mid);     // 左边部分排序后逆序数
        int right_count = mergeSort(array, mid+1, end);    // 右边部分排序后逆序数

        int i = mid, j = end; // 记录中间值和结束值的索引
        int[] copy = new int[end - start + 1];  // 创建当前处理数据的长度的一个数组
        int copy_index = end - start;           // 定位 新数组的最后位置的索引
        int count = 0;                          // 统计                
        // left :从mid到start  right: end 到  mid +1
        while (i >= start && j >= mid + 1){
            // 出现逆序对
            if (array[i] > array[j]){
                copy[copy_index --] = array[i--]; // copy数组拷贝
                count += j - mid;  // 个数计算
                // 数据过大处理
                if (count > 1000000007){
                    count %= 1000000007;
                }
            }else {
                copy[copy_index --] = array[j --]; // copy数组拷贝
            }
        }
        // 如果一个比完了,另一个没有比完,继续复制
        while (i >= start){
            copy[copy_index--] = array[i--];
        }
        // 如果一个比完了,另一个没有比完,继续复制
        while (j>= mid + 1){
            copy[copy_index--] = array[j--];
        }
        i = 0;
        while (start <= end){
            array[start ++] = copy[i++]; // 将数据copy进去(完成排序)
        }
        return (left_count + right_count + count)%1000000007;
    }
}

Python

这道题在牛客网上比较难通过,通过的代码也让人感觉和玄学一样,代码如下可做参考,我也不理解,希望有懂得大,能分享一下:

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        return 24903408 if data[0]==26819 else 493330277 if data[0]==627126 else 988418660 if data[0]==74073 else 2519

###

正文到此结束
本文目录