微学网

热门关键词:   as  thinkphp  ecshop  xxx  商务通  www.ymwears.cn
热门: ASP.NET PHP编程 ASP编程 JSP编程 Python

剑指offer之面试题51:数组中的逆序对

发布时间:2021-04-22 来源:未知 点击:

面试题51:数组中的逆序对

题目:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。例如,在数组{7, 5, 6, 4}中,一共存在5个逆序对,分别是(7, 6)(7,5)(7,4)(6, 4)和(5, 4)。

思路:

在这里插入图片描述
 

代码实现:

package Question51;

import java.util.Arrays;

public class T01 {

    static int count;

    public static void main(String[] args) {
        int[] arr = {7, 5, 6, 4};
        System.out.println(solve(arr));
    }

    public static int solve(int[] arr) {
        if(arr == null && arr.length == 0) return count;
        int left = 0, right = arr.length-1;
        divide(arr, left, right);
        return count;
    }

    public static void divide(int[] arr, int left, int right) {
        //说明只有1个元素
        if(left == right) return ;
        int mid = left + (right - left) / 2;
        divide(arr, left, mid);
        divide(arr, mid+1, right);
        merge(arr, left, mid, mid+1, right);
    }

    public static void merge(int[] arr, int left1, int right1, int left2, int right2) {
        int[] arr1 = Arrays.copyOfRange(arr, left1, right1+1);
        int[] arr2 = Arrays.copyOfRange(arr, left2, right2+1);
        int p1 = arr1.length - 1, p2 = arr2.length - 1, p3 = right2;
        while(p1 >= 0 && p2 >= 0) {
            if(arr1[p1] > arr2[p2]) {
                count += p2 + 1;
                arr[p3--] = arr1[p1--];
            } else arr[p3--] = arr[p2--];
        }
        while(p1 >= 0) arr[p3--] = arr1[p1--];
        while(p2 >= 0) arr[p3--] = arr2[p2--];
    }
}

 

这就是微学网-程序员之家为你提供的"剑指offer之面试题51:数组中的逆序对"希望对你有所帮助.本文来自网络,转载请注明出处:http://www.weixuecn.cn/article/14256.html
网络编程 | 前端制作 | 数据库 | CMS教程 | 脚本编程 | 框架 | 服务器 | 微信开发 | APP开发 | 学习教程 |

凡本网站转载的文章、图片等资料的版权归版权所有人所有,因无法和版权所有者一一联系,如果本网站选取的文/图威胁到您的权益,请您及时和本网站联系。 我们会在第一时间内采取措施,避免给双方造 成不必要的损失。
© 2015-2021 微学网 版权所有,并保留所有权利。 备案号:粤ICP备09051474号-1

菜鸟学习网,提供各类程序编程入门,技巧