合併排序解決任務

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複雜，所以我們不看都對。