合并排序解决任务

Question

我有一个ArrayList大小为10^5。我想计算一行中的数字对Pi和Pj，其中Pi在该行中的Pj之前，并且Pi具有比Pj更大的值。

CODE

public void sort(ArrayList<Integer> finalarray, int size) 
     { 
      if(finalarray.size()<2) return ; 

      ArrayList<Integer> right = new ArrayList<>(); 
      ArrayList<Integer> left = new ArrayList<>(); 
      int mid = finalarray.size()/2; 
      for(int i=0;i<mid;i++) left.add(finalarray.get(i)); 
      for(int j=mid;j<size;j++) right.add(finalarray.get(j)); 

      sort(left, left.size()); 
      sort(right, right.size()); 

      int l=0, r=0 , m =0; 
      int temp=-1; 
      while(l< left.size() && r< right.size()) 
      { 
        if(left.get(l)> right.get(r)) 
        { 
         finalarray.set(m, right.get(r)); 
        if(temp!=l) 
         answer+=r+1; 
        if(temp==l) 
         answer++; 
         r++; 

         temp=l; 
        } 
        else 
        { 
        finalarray.set(m, left.get(l)); 
         l++; 
        } 
        m++; 
      } 
      while(l< left.size()) 
      { 
       finalarray.set(m, left.get(l)); 
       l++; 
       m++; 
       answer+=right.size(); 
      } 
      while(r< right.size()) 
      { 
       finalarray.set(m, right.get(r)); 
       r++; 
       m++; 
      } 
} 

实施例： 阵列：1，2，4，第7，5,3
答案：4
（4和3），（7和5），（ 7和3），（5和3）。
我正在使用合并排序，但我没有得到正确的答案。
请解释我做错了什么。

Answer 1

有一个快速浏览一下你的代码，我相信，这些线是什么给你错误的结果：

if (temp!=l) 
    answer+=r+1;` 

我看不出这有什么。如果你删除它，你会得到正确的结果。

但是，我认为合并排序不适合解决这个问题。看看这个例子：

对于列表5 4 3 4正确的答案应该是4，现在让我们看看，什么归并排序会做这个名单考虑你的方法：

5 4 | 3 4结果0

5 | 4 | 3 | 4结果0

4 5 | 3 4结果1

3 || 4 5 | 4结果2

3 4 || 5 | 4结果2

3 4 4 || 5 |结果3

3 4 4 5 || |结果3

现在，如果你想一想，归并排序确实有一个的n*log n复杂，所以我们不看都对。