题解 | #数组中的逆序对#

思路1
递归，dp(n) = dp(n-1)+[n到n-1]之间比n小的和，例如，遍历数组，第一个数是5，则判断4是否在右侧，如果有，则统计IDX5到IDX4之间比5小的值的个数，并获得4的索引IDX4，递归计算4右侧逆序数量。
用HashMap可以加快递归过程，递归获得4右侧的逆序数量时，先从hashMap中找4是否已经计算过，如果已经计算过，则直接读取计算的结果值，否则递归调用3右侧逆序数量。（但就是利用了HashMap还是会运行超时，哎。。。）
自测运行可以通过，但正式提交时运行超时。

import java.util.HashMap;
public class Solution {
  class Content{
      public int num;
      public int idx;
      public Content(int inNum, int inIdx){
          num = inNum;//当前数组元素的逆序对数目
          idx = inIdx;//当前数组元素的索引值
      }
  }
  public int InversePairs(int [] array) {
      if(array.length == 0) return 0;
      int res = 0;
      //构建字典
      int iHashMapSize =(int)((float)array.length/0.75f+1);
      HashMap<Integer,Content> mapArray = new HashMap<Integer,Content>(iHashMapSize);
      int iMinValue = array[0];
      for(int idx = 0; idx < array.length; ++idx){
          Content tmpC = new Content(-1,idx);
          mapArray.put(array[idx],tmpC);
          if(iMinValue >array[idx]) iMinValue = array[idx];
      }

      //计算结果值
      for(int idx = 0; idx<array.length;++idx){
          res+=CalTimes(mapArray,array,array[idx],iMinValue);
      }
      return res;
  }

  int CalTimes(HashMap<Integer,Content> mapArray,int [] array,int inValue,int inMinValue){
      //如果是数组中最小值，则右侧比最小值小的值为0
      if(inValue == inMinValue) return 0;
      Content c = mapArray.get(inValue);
      if((c.num)!=-1){
          //已经计算过，则返回已经计算过的值
          return c.num;
      }
      //没有统计过该值，则计算该值右侧比该值小的数有多少个
      //当前Value的idx
       int curValueIdx = c.idx;
       int nextValueIdx = 0;
      int curValue = inValue;
      while(false == mapArray.containsKey(curValue-1)
           ||  mapArray.get(curValue-1).idx < curValueIdx){
          if(true == mapArray.containsKey(curValue-1)){
              nextValueIdx = mapArray.get(curValue-1).idx ;
          }
          if((curValue-1) == inMinValue) break;
          --curValue;
      }
      nextValueIdx = mapArray.get(curValue-1).idx ;
      int curNum = 0;
      int ptValue = curValue;

      if( mapArray.get(curValue-1).idx < curValueIdx){
          curNum = 0;
      }
      else{
          //在curValueIdx和NextValueIdx之间还有n个小于curValue的值
          for(int idx = curValueIdx; idx < nextValueIdx; ++idx){
              if(array[idx] <inValue){
                  ++curNum;
              }
          }
          curNum += ((CalTimes(mapArray,array,curValue-1,inMinValue)+1)%1000000007);
      }
      c.num =curNum;
      return curNum;
  }
}

正确思路1
归并排序
引申：遇到区间问题都可以用归并来求解，但区间问题的具体定义是什么呢？

public class Solution {

  private int cnt;
  public int InversePairs(int [] array) {
      if(array.length == 0) return 0;
      int []temp = new int[array.length];
      return sort(array,0,array.length-1,temp);
      //return cnt;
  }

  int sort(int [] array,int inStart, int inEnd,int []temp){
      if(inStart < inEnd){
          int mid = (inStart+inEnd)/2;
          int res1 = sort(array,inStart,mid,temp);
          int res2 = sort(array,mid+1,inEnd,temp);
          /*二分法的左右区间处理，右区间的起始可以+1开始，
          这样可解决在2,3之间算mid，mid = 2时，有区间是[2,3]的情况
          */
          int res3 = merge(array,inStart,mid,inEnd,temp);
          return (res1+res2+res3)%1000000007;
      }
      return 0;
  }
  int merge(int []array ,int inStart,int inMid,int inEnd, int[]temp){
      int res = 0;
      int i = inStart;//含右，因为inEnd也是有效值
      int j = inMid+1;
      int k = inStart;
      while(i <= inMid && j <= inEnd){
          if(array[i] <= array[j]){
              temp[k++] = array[i++];
          }
          if(array[i] > array[j]){
              res = (res + (inMid-i+1))%1000000007;
              temp[k++] = array[j++];
             /* temp[k++] = array[j++];
              cnt = (cnt + (inMid-i+1))%1000000007;*/
          }
      }
      //把剩下的接到temp中
      while(i <=inMid){
          temp[k++] = array[i++];
      }
      while(j <=inEnd){
          temp[k++] = array[j++];
      }
      //将当前array区间覆盖为有序的temp
      for(int l = inStart; l <k;++l){
          array[l] = temp[l];
      }

      return res;
  }
}

防吞格式
防吞格式
防吞格式
防吞格式
防吞格式
防吞格式
防吞格式