java简单实现数组中的逆序对

题目描述：

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

解题思路：

一开始一头雾水，后面想到了使用归并排序的思想，其实有多少个逆序对，就是归并排序的时候，后面的数要超越前面多少个，嗯，好像不是很好说，要不然直接看代码吧。还要注意，题目当中说要输出取模的结果，这说明数据可能非常大，所以如果只是单纯的在最后取模的话可能还是无法避免数据太大的影响，所以我们在每次更新count的时候就对其进行取模运算。

刚好又练习了一遍归并排序，记录一下

public class Solution {
  int count;
  public int InversePairs(int [] array) {
    count = 0;
    if(array != null){
      divPairs(array, 0, array.length-1);
    }
    return count%1000000007;
  }

  public void divPairs(int[] array, int start, int end){
    if(start >= end)
      return;
    int mid = (start + end)>>1;
    divPairs(array, start, mid);
    divPairs(array, mid+1, end);

    mergePairs(array, start, mid, end);
  }

  public void mergePairs(int[] array, int start, int mid, int end){
    int i = start, j = mid+1, k = 0;
    int[] temp = new int[end-start+1];
    while(i <= mid && j <= end){
      if(array[i] <= array[j]){
        temp[k++] = array[i++];
      }else{
        temp[k++] = array[j++];
        count += mid - i + 1;
        count %= 1000000007;
      }
    }
    while(i <= mid){
      temp[k++] = array[i++];
    }
    while(j <= end){
      temp[k++] = array[j++];
    }
    for(int x = 0; x < temp.length; x++){
      array[start+x] = temp[x];
    }
  }
}

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

赞 (0)

相关推荐

  • java实现左旋转字符串

    汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果.对于一个给定的字符序列S,请你把其循环左移K位后的序列输出.例如,字符序列S="abcXYZdef",要求输出循环左移3位后的结果,即"XYZdefabc".是不是很简单?OK,搞定它! 代码 解法一 最直观的方式,依次将需要移位的字符移动至最后,但是每个字符都需要移动数组的长度-1,如果数组的长度是n,需要移k位,则总共需要移动 k * (n - 1) publ

  • java中线程的状态学习笔记

    java开发中,我们经常会遇到线程的问题,比如你做一个商城,就需要考虑它的并发问题等等,今天给大家分享一下java中线程的状态 先说线程的第一个状态,是新建状态,这个是线程刚刚创建的时候,如: new Thread(),具体如图 线程的第二种状态是可执行状态,就是调用了start方法后的状态,当然了,一个运行的状态,他有可能是正在运行的,也有可能是没有运行的,只是他的状态是可运行的状态,具体如图 第三种状态是被阻塞或者处于等待的线程,处于这种状态下的线程是不活动且不运行的,比如说调用了wait方

  • java.util.Collection源码分析与深度理解

    java.util.Collection源码分析与深度理解

    写在开头 java.util.Collection 作为Java开发最常用的接口之一,我们经常使用,今天我带大家一起研究一下Collection接口,希望对大家以后的编程以及系统设计能有所帮助,本文所研究的jdk版本为jdk1.8.0_131 明确一下几点: Collection是接口,其继承了Iterable接口 Collection属于单值类型集合,重点子接口List接口和Set接口 Java.util.List接口(有序.不唯一) ArraryList ArrayList 是一个数组队列,

  • 理解 Java 核心基础精髓解析

    1.字符串不变性 下面这张图展示了这段代码做了什么 String s = "abcd"; s = s.concat("ef"); 2.equals() 方法与 hashCode() 方法的区别 HashCode 被设计用来提高性能.equals() 方法与 hashCode() 方法的区别在于: 如果两个对象相等(equal),那么他们一定有相同的哈希值. 如果两个对象的哈希值相同,但他们未必相等(equal). 3.Java异常类的层次结构 图中红色部分为受检查异

  • Java构建乘积数组的方法

    Java构建乘积数组的方法

    本文实例为大家分享了Java构建乘积数组的具体实现代码,供大家参考,具体内容如下 给定一个数组A[0,1,-,n-1],请构建一个数组B[0,1,-,n-1],其中B中的元素B[i]=A[0]A[1]-A[i-1]*A[i+1]-*A[n-1]. 不能使用除法. 代码 解法一 暴力法,这是本能就能想到的解决办法. public static int[] multiply(int[] array) { if (array == null) { return null; } int len = ar

  • java实现翻转单词顺序列

    本文实例为大家分享了java实现翻转单词顺序列的具体代码,供大家参考,具体内容如下 最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上.同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思.例如,"student. a am I".后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是"I am a student.".Cat对一一的翻转这些单词顺序可不在行,你能帮助他么? 代码 借助上一篇文章左旋

  • java简单实现数组中的逆序对

    题目描述: 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对.输入一个数组,求出这个数组中的逆序对的总数P.并将P对1000000007取模的结果输出. 即输出P%1000000007 解题思路: 一开始一头雾水,后面想到了使用归并排序的思想,其实有多少个逆序对,就是归并排序的时候,后面的数要超越前面多少个,嗯,好像不是很好说,要不然直接看代码吧.还要注意,题目当中说要输出取模的结果,这说明数据可能非常大,所以如果只是单纯的在最后取模的话可能还是无法避免数据太大的影

  • 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 ||

  • java面试题之数组中的逆序对

    java面试题之数组中的逆序对

    题目:在数组中的两个数字如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对.输入一个数组,求出这个数组中的逆序对的总数 例如在数组{7,5,6,4}中,一共存在5对逆序对,分别是{7,6},{7,5},{7,4},{6,4},{5,4}. 看到这个题目,我们的第一反应就是顺序扫描整个数组.每扫描到一个数组的时候,逐个比较该数字和它后面的数字的大小.如果后面的数字比它小,则这两个数字就组成一个逆序对.假设数组中含有n个数字.由于每个数字都要和O(n)个数字做比较,因此这个算法的时间复杂度为

  • java 从int数组中获取最大数的方法

    首先要有数组的概念吧,知道什么是数组,简单讲就是存放一组数据的一个组合,就是一个数组....哈哈 已知一个int数组, 编程从数组中获取最大数. 思路分析: 1.一个数组可能有很多个数字,要取最大数,那就是一个数一个数的进行比较可以可以选出来了是吧 那么就是:先定义一个变量赋值为数组的第一个数,然后在和数组的第二.第三个数相比较,遇到比自己大的就将打的数值赋给这个变量,遍历到最后就可以了. 代码: package com.itheima; /** * 2. 已知一个int数组, 编程从数组中获取

  • JS简单去除数组中重复项的方法

    JS简单去除数组中重复项的方法

    本文实例讲述了JS简单去除数组中重复项的方法.分享给大家供大家参考,具体如下: <!DOCTYPE html> <html lang="zh-cn"> <head> <meta charset="UTF-8"> <title></title> </head> <body> <script> var arr = ["aaa","bb

  • Java简单统计字符串中汉字，英文字母及数字数量的方法

    本文实例讲述了Java简单统计字符串中汉字,英文字母及数字数量的方法.分享给大家供大家参考,具体如下: package org.zhy.demo.algorithm; /** * 有一个字符串,其中包含中文字符.英文字符和数字字符,请统计和打印出各个字符的个数 * * @author Administrator * */ public class Str { public static void main(String[] args) { String str = "adasfAAADFD阿萨德

  • Java替换int数组中重复数据的方法示例

    本文实例讲述了Java替换int数组中重复数据的方法.分享给大家供大家参考,具体如下: package test; import java.util.HashSet; public class TestList { /** * 根据传递过来的参数过滤掉重复数据 * @param number:需要过滤掉的数据 * @return:筛选好的新数组 */ public static int[] Filter(int[] number){ HashSet<Integer> hs=new HashSe

  • java 判断一个数组中的数值是否连续相邻的方法

    * 判断一个数组中的数值是否连续相邻 * 满足以下条件: * 1.0是例外可以反复出现 0可以通配任何字符 * 2.相同的数值不会重复出现 * 3.该数组可以是乱序的 * 当数组不含有0时满足最大值-最小值=n(数组长度)-1 * 当数组数组含有0时.满足最大值-最小值<n(数组长度)-1 * 所以,当最大值最大值-最小值>n(数组长度)-1时,一定不是连续相邻数组 package datastruct.usearray; public class JudgeAdjacent { privat

  • java简单实现数组的增删改查方法

    目录 1.一维数组​ 2.数组的扩容 3.数组的复制 1.直接将数组赋值给新数组 2.创建一个新的数组,再将原数组的数据逐个赋值 4.数组的删除 5.数组的排序 6.数组的查找 1.顺序查找:从头到尾遍历(简单除暴,效率相对较低) 2.二分法查找 总结 1.一维数组​ 概念:一组数据的容器(数组可以存放多个数据) ​ 注意: ​ 1.数组是引用数据类型 ​ 2.数组中的数据又叫做元素 ​ 3.每个元素都有编号叫做下标/索引 ​ 4.下标从0开始 ​ 5.数组初始化后,会在内存中开辟一连串连续的空

  • Java数组中的元素删除并实现向前移的代码

    废话不多说了,直接给大家贴代码了. 具体代码如下所示: public class Test { /** * Java怎么删除数组中的一个元素并且向前移 * * @param args * @throws IOException */ public static void main(String[] args) { String[] arrays = { "", "", "", "", "" }; Syste

随机推荐