专栏首页Java小白成长之路逆序对-----归并排序

逆序对-----归并排序

本周遇到了一道蛮有意思的题目,分享给大家欣赏一下!这道题使用归并排序。原来在力扣上刷题时,也遇到过一次归并的思路,不过当时一知半解,就跳过去了,心想着以后遇到了再深究一下,结果很快就遇到了----天注定啊!那我们这次一起来看看这个排序思想吧!


我们首先来介绍一下归并排序!

归并排序

归并排序主要是对一个无序的数组进行不断的对半切分为更小的数组,直到最小的数组元素个数为0或1,然后再将所有被切分的元素进行重新排序,每一次都会得到一个新的有序小数组,最后将这些小的有序数组合并起来,得到一个最终整体有序的数组。我们来看一下整个过程的示意图:

归并排序示意图

数组中的逆序对

《剑指offer》--------- 数组中的逆序对 题目描述

题目描述

简单的说就是给定一个数组,数组中每个元素的前面都有k个大于当前元素的数,将每个元素的k相加,得到整个数组的逆序对。

1、解决思路

解决这道题目可以使用经典的排序算法------归并排序。

对于本题,我们可以将其进行一个转化:利用归并算法,将数组A进行排序,在分割的时候,直到数组的元素个数为0或1,才开始进行排序,所以在排序的过程中,逐一去对比左右数组的元素大小,如果left[i]>right[j],则在当前合并过程中,对于right[j]的逆序对为left[i]~left[end-1]

由此我们便解决了当前的问题。

2、代码实现

public class Solution {
    int res = 0;
    //使用归并思路
    public int InversePairs(int [] array) {
        MergeCut(array,0,array.length-1);
        return res;
    }
    //分割
    private void MergeCut(int[] array, int start, int end){
        if(start >= end){
            return;
        }
        int mid = (end-start)/2 + start;
        MergeCut(array,start,mid);//left
        MergeCut(array,mid+1,end);//right
        MergeSort(array,start,mid,end);
    }
    //排序
    private void MergeSort(int[] array, int start, int mid, int end){
        int[] temp = new int[end - start + 1];
        int left = start, right = mid+1, index = 0;
        while(left <= mid && right <= end){
            if(array[left] > array[right]){
                res = (res + mid - left + 1)%1000000007;
                temp[index++] = array[right++];
            }else{
                temp[index++] = array[left++];
            }
        }
        while(left <= mid){
            temp[index++] = array[left++];
        }
        while(right <= end){
            temp[index++] = array[right++];
        }
        //将temp赋值给原数组array
        for(int i = 0 ; i < temp.length ; i++){
            array[start++] = temp[i];
        }
    }

本文分享自微信公众号 - Java小白成长之路(Java_xiaobai),作者:鹏程万里

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 字符串排序---字典序

    本周我们分享一个获取全排列的算法。这道题当时也是花了蛮久的时间才跟着题解写出来!小白经历了这道题目的“煎熬”之后,就为大家保驾护航,一起轻松拿下此题吧!

    鹏-程-万-里
  • 第23次文章:结构性模式

    前面三期我们主要介绍了4中创建型模式:单例模式、工厂模式、建造者模式、原生模式。这周我们开始进入下一大块儿的模式学习——结构性模式。

    鹏-程-万-里
  • 第26次文章:正则表达式

    一种强大而灵活的文本处理工具。大部分编程语言、数据库、文本编辑器、开发环境都支持正则表达式

    鹏-程-万-里
  • 二路归并排序的java实现

    转载请注明出处 http://www.cnblogs.com/dongxiao-yang/p/6410775.html

    sanmutongzi
  • 希尔排序

    如果上一篇初级排序算法中的插入排序你已经熟悉,那么今天的这个希尔排序对你来说就要简单一些。希尔排序,就是使用不同增量进行一遍一遍的插入排序的排序算法。首先,增量...

    naget
  • numpy 矩阵形状调整:拉伸、变成一位数组的实例

    补充知识:numpy ndarray 形状(shape)变换(reshape)变形

    砸漏
  • 总结5种比较高效常用的排序算法

    1 概述     本文对比较常用且比较高效的排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性...

    闵开慧
  • 总结五种常见的排序算法

        本文对比较常用且比较高效的排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性能比较如下...

    Kevin_Zhang
  • 朴素贝叶斯分类器的应用

    本文介绍朴素贝叶斯分类器(Naive Bayes classifier),它是一种简单有效的常用分类算法。

    bear_fish
  • 朴素贝叶斯分类器的应用

    生活中很多场合需要用到分类,比如新闻分类、病人分类等等。 本文介绍朴素贝叶斯分类器(Naive Bayes classifier),它是一种简单有效的常用分类算...

    ruanyf

扫码关注云+社区

领取腾讯云代金券