剑指offer—数组逆序对 解答

剑指offer—数组逆序对

题目描述

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

题目保证输入的数组中没有的相同的数字

数据范围:

    对于%50的数据,size<=10^4

    对于%75的数据,size<=10^5

    对于%100的数据,size<=2*10^5

思路

使用归并排序,在当左数组顶部元素比右数组顶部元素大的时候,逆序对数count值需要增加

我们每次合并需要建立一个新数组来保存制定位置的值,并且最后添加到原数组中

  • 合并时比较:比较两个数组的头部的值,右边大就正常顺序添加元素,然后右边头往右边移动一位;左边大就把把右边头部元素添加到数组再把左边头部元素添加到数组(因为左右数组内都已排好序,头部为最小值)

我们通过下面图来判断合并时需要count增加的值:

1570526246579

最后以此合并对应流程:start为左边标号,index为右边标号,初始start=0,index=mid+1

  • 1.0<1 插入0,start++
  • 2.3>1 插入1 index++ count+=4-1
  • 3.3>2 插入2 index++ count+=4-1
  • 4.3<4 插入3 start++
  • 5.5>4 插入4 index++ count+=4-2
  • 6.5<7 插入5 start++
  • 7.6<7 插入6 start++
  • 8.插入7

代码

public class Solution {
    int count = 0;
    public int InversePairs(int [] array) {
        if(array.length==0) return 0;
        sortMerge(array,0,array.length-1);
        return count;
    }
    public void sortMerge(int []a,int start,int end){
        if(start<end){
            int mid = (end+start)/2;
            sortMerge(a,start,mid);
            sortMerge(a,mid+1,end);
            merge(a,start,mid,end);
        }
    }
    public void merge(int[] a,int start,int mid,int end){
        int c = 0;//用于新数组插入累加计数
        int s = start;//用于左边标号递增
        int index = mid+1;
        int [] num = new int[end-start+1];//新数组的头对应数组start处,end为尾处
        while(start<=mid&&index<=end){
            if(a[start]>a[index]){
                num[c++] = a[index++];
                count += mid+1-start;
                count %= 1000000007;//当count过大超过1000000007时,对它求余,减小数
            }else{
                num[c++] = a[start++];
            }
        }
        while(start<=mid){
            num[c++] = a[start++];
        }
        while(index<=end){
            num[c++] = a[index++];
        }
        for(int n:num){
            a[s++] = n;//对应位置插入,从start开始,依次累加
        }
    }
}

扩展—LeetCode315计算右侧小于当前元素的个数

题目描述

给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

思路

我们使用count数组保存每个元素右侧小于该值的个数,最后把数组中的值全部添加到list集合中

使用归并排序,在每一次合并时,如果比较的右边值小的话,就要把startmid的count结果累加1

难点:

每次合并数组位置发生变化,使用下标进行累加的话会出现错误,我们需要记录每个元素对应位置的索引

  • 不存在重复数字时,可以使用hash表保存每个数对应元素的索引
  • 存在重复元素时,我们不能使用hash表,可以使用索引数组来保存对应元素的索引,我们只对索引数组进行位置变化,原数组保持不变,我们就可以拿到索引数组的索引再去原数组找对应的元素

代码

  • 不存在重复数字的情况
class Solution {
    List<Integer> list = new ArrayList<>();
     Map<Integer,Integer> map = new HashMap<>();//hash保存元素索引
    public List<Integer> countSmaller(int[] array) {
        if(array.length==0) return list;
        in = new int[array.length];
        for(int i=0;i<array.length;i++){
            list.add(0);
             map.put(array[i],i);
        }
        sortMerge(array,0,array.length-1);
        return list;
    }
    public void sortMerge(int []a,int start,int end){
        if(start<end){
            int mid = (end+start)/2;
            sortMerge(a,start,mid);
            sortMerge(a,mid+1,end);
            merge(a,start,mid,end);
        }
    }
    public void merge(int[] a,int start,int mid,int end){
        int c = 0;
        int s = start;
        int index = mid+1;
        int [] num = new int[end-start+1];
        while(start<=mid&&index<=end){
            if(a[start]>a[index]){
                num[c++] = a[index++];
                //归并时比较右边值小的话,进行累加,时间复杂度稍高
                for(int i=start;i<=mid;i++){
                     int f = map.get(a[i]);
                    list.set(f,list.get(f)+1);
                }
            }else{
                num[c++] = a[start++];
            }
        }
        while(start<=mid){
            num[c++] = a[start++];
        }
        while(index<=end){
            num[c++] = a[index++];
        }
        for(int n:num){
            a[s++] = n;
        }
    }
}
  • 存在重复数字的情况
class Solution {
    List<Integer> list = new ArrayList<>();
    //索引数组
    int [] in = null;
    //保存原数组
    int [] a = null;
    //计数数组
    int [] count = null;
    public List<Integer> countSmaller(int[] array) {
        if(array.length==0) return list;
        in = new int[array.length];
        count = new int[array.length];
        a = array;
        for(int i=0;i<array.length;i++){
            in[i] = i;
        }
        sortMerge(in,0,array.length-1);//只对索引数组变化,原数组保持不变
        for(int c:count){
            list.add(c);
        }
        return list;
    }
    public void sortMerge(int []in,int start,int end){
        if(start<end){
            int mid = (end+start)/2;
            sortMerge(in,start,mid);
            sortMerge(in,mid+1,end);
            merge(in,start,mid,end);
        }
    }
    public void merge(int[] in,int start,int mid,int end){
        int c = 0;
        int s = start;
        int index = mid+1;
        int [] num = new int[end-start+1];//不能直接修改索引数组,需要用新数组保存,归并一次结束后再写入索引数组
        while(start<=mid&&index<=end){
            if(a[in[start]]>a[in[index]]){//用索引数组的值判断原数组的值
                num[c++] = in[index++];
                //执行计数累加操作
                for(int i=start;i<=mid;i++){
                    count[in[i]]++;
                }
            }else{
                num[c++] = in[start++];
            }
        }
        while(start<=mid){
            num[c++] = in[start++];
        }
        while(index<=end){
            num[c++] = in[index++];
        }
        //归并一次把变化写入到索引数组
        for(int n:num){
            in[s++] = n;
        }
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/desc-pair.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!