java实现数组中的逆序对

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对,例如在数组{7,5,6,4}中,一共存在5对逆序对,分别是{7,6},{7,5},{7,4},{6,4},{5,4}。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。,即输出P%1000000007。

代码

解法一

暴力简单低效,不会改变原数组

public static int inversePairs(int[] array) {
    if (array == null || array.length < 2) {
      return 0;
    }
    int count = 0;
    for (int i = 0; i < array.length; i++) {
      for (int j = i + 1; j < array.length; j++) {
        if (array[i] > array[j]) {
          count++;
        }
      }
    }
    return count % 1000000007;
  }

解法二

利用数组的归并排序,高效,但是会改变原数组

public static int inversePairs2(int[] array) {
    if (array == null || array.length < 2) {
      return 0;
    }
    int count = mergeSort(array, 0, array.length - 1);
    return count % 1000000007;
  }

  private static int mergeSort(int[] array, int start, int end) {
    if (start >= end) {
      return 0;
    }

    // 找到数组的中点,分割为两个子数组,递归求解
    int middle = (start + end) / 2;
    int left = mergeSort(array, start, middle);
    int right = mergeSort(array, middle + 1, end);

    // 存储归并后的数组
    int[] copy = new int[array.length];
    System.arraycopy(array, start, copy, start, end - start + 1);
    // 从两个子数组的尾部开始遍历
    int i = middle;
    int j = end;
    int copyIndex = end;
    // 记录逆序对的数量
    int count = 0;

    while (i >= start && j >= middle + 1) {
      // 数组是升序的
      // 如果左边数组比右边数组大,则将大的放入存储数组中
      // 并且累加逆序对,应为是有序的,所以左边数组的第i个元素比第j个及其之前的数都大
      if (array[i] > array[j]) {
        copy[copyIndex--] = array[i--];
        count += (j - middle);
      } else {
        copy[copyIndex--] = array[j--];
      }
    }

    // 将子数组剩余的部分一次写入归并后的存储数组
    while (i >= start) {
      copy[copyIndex--] = array[i--];
    }
    while (j >= middle + 1) {
      copy[copyIndex--] = array[j--];
    }

    // 将本次两个子数组的合并写入原数组中
    for (int k = start; k <= end ; k++) {
      array[k] = copy[k];
    }
    return left + right + count;
  }

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Java中数组在内存中存放原理的讲解

    Java中数组被实现为对象,它们一般都会因为记录长度而需要额外的内存.对于一个原始数据类型的数组,一般需要24字节的头信息再加上保存值所需的内存,其中24字节的头信息分别包含以下几个部分. 下面分别分析一维.二维.三维的数组存储情况. 下面首先对一维数组进行分析,以int[]型数组为例,假设数组长度为N,那么需要的内存占用(24+4N)个字节,原因分析比较简单,图解示例如下:即占用内存总量=头信息内存+数组N个int值占用内存. 对于二维数组进行分析,首先对于多维数组的概念,大家可以参考这篇文章

  • Java实现删除排序数组中重复元素的方法小结【三种方法比较】

    本文实例讲述了Java实现删除排序数组中重复元素的方法.分享给大家供大家参考,具体如下: 题目描述: 给定一个排序数组,在原数组中删除重复出现的数字,使得每个元素只出现一次,并且返回新的数组的长度. 不要使用额外的数组空间,必须在原地没有额外空间的条件下完成. 一:通过ArrayList解决 时间复杂度和空间复杂度都为O(n) ArrayList<Integer> list = new ArrayList<Integer>(); // 去掉数组中重复的元素 public int r

  • Java中字符数组和字符串与StringBuilder和字符串转换的讲解

    1.字符串->字符数组: String str = "abc": char[] a = str.toCharArray(); 记忆:字符串是个类,所以用内建函数 延伸: char b = str.charAt(1); str.length(); a.length; 2.字符数组->字符串: String str = String.valueOf(a): 记忆:类似强制类型转换格式,String(a) 延伸:字符转字符类 Character c = Character.val

  • java实现二分法查找出数组重复数字

    本文实例为大家分享了java实现二分法查找出数组重复数字的具体代码,供大家参考,具体内容如下 package offer; /** * 二分查找的思想来找到数组中重复的数字,时间复杂度在o(nlogn)-o(n^2) */ public class FindDuplicate3 { public static void main(String[] args) { int numbers[] = {0,1,2,3,4,4,6,7};//数组中的数 大小从0 到 numbers.length-1 f

  • Java算法实现调整数组顺序使奇数位于偶数之前的讲解

    调整数组顺序使奇数位于偶数之前 1. 题目描述 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变. 2. 题目分析 该题目类似于一个选择排序,将奇数选择出来,放置于数据前面的位置,保持其他未被选择的元素的相对位置不变: 1. 遍历数组,当数组元素为奇数是进行处理,判断条件为 n % 2 != 0 2. 设置一个变量标注当前已遍历的元素中奇数的个数oddNum,也是将该奇数元素

  • 浅谈JAVA实现选择排序,插入排序,冒泡排序,以及两个有序数组的合并

    一直到大四才开始写自己的第一篇博客,说来实在有点羞愧.今天写了关于排序的算法题,有插入排序,冒泡排序,选择排序,以下贴上用JAVA实现的代码: public class test5 { public static void print(int []array) //输出数组方法 { for(int i=0;i<array.length;i++) System.out.print(" "+array[i]); } public static void selectsort(int

  • Java Scanner输入两个数组的方法

    题目 从命令行读入两个数组的长度和数组的值,其中第一行两个数na和nb代表aa和bb数组的长度 代码 import java.util.Scanner; public class Z { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int na = scanner.nextInt(); int nb = scanner.nextInt(); int[] aa = new in

  • Java数组高级算法与Arrays类常见操作小结【排序、查找】

    本文实例讲述了Java数组高级算法与Arrays类常见操作.分享给大家供大家参考,具体如下: 冒泡排序 冒泡排序原理 冒泡排序代码: package cn.itcast_01; /* * 数组排序之冒泡排序: * 相邻元素两两比较,大的往后放,第一次完毕,最大值出现在了最大索引处 */ public class ArrayDemo { public static void main(String[] args) { // 定义一个数组 int[] arr = { 24, 69, 80, 57,

  • java集合与数组的相同点和不同点

    数组: 数组可以用来保存多个基本数据类型的数据,也可以用来保存多个对象. 数组的长度是不可改变的,一旦初始化数组时就指定了数组的长度(无论是静态初始化还是动态初始化). 数组无法保存具有映射关系的数据. 集合: 集合是只用于存储数量不等的对象. 集合的长度是可变的. 集合可以保存具有映射关系的数据. 相同点: 数组和集合类同是容器. 不同点: 数组的长度是固定的,集合的长度是可变的. 数组只能存储同类型的对象,集合可以存储不同类型的对象. 集合只能存储对象不能存储基本类型 总结 以上就是这篇文章

  • Java如何找出数组中重复的数字

    题目描述:找出数组中重复的数字,具体内容如下 在一个长度为n的数组里的所有数字都在 0~n-1的范围内.数组中某些数字是重复的,但不知道有几个数字是重复的,也不知道每个数字重复了几次.请找出数组中任意一个重复的数字.例如:如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出的是重复的数字2或者3 这个面试题是剑指offer中的面试题3,,下面我用java代码实现. 算法步骤: 从头到尾依次扫描数组中的每个数字. 1. 当扫描到下表为i的数字时,首先比较这个数字(用m表示)是不是等

随机推荐