計數在尺寸<code>n</code>的陣列<code>a</code>反轉以陣列C++

反演的數量，被稱爲對(i,j)對於其認爲i<j和a[i]>a[j]。我試圖在C++中實現一個函數，它計算給定數組中的反轉次數。我遵循分而治之的方法，它只是修改合併排序算法，並在O（n log n）時間運行。這是我到目前爲止的代碼：計數在尺寸<code>n</code>的陣列<code>a</code>反轉以陣列C++

long long int glob; 

template< class T > 
long long int merge(T *arr, int beg, int mid, int end) { 
    queue<int> left; 
    queue<int> right; 

    for(int i=beg; i<=mid; ++i) { 
    left.push(arr[i]); 
    } 
    for(int i=mid+1; i<=end; ++i) { 
    right.push(arr[i]); 
    } 

    int index=beg; 
    int ret=0; 

    while(!left.empty() && !right.empty()) { 
    if(left.front() < right.front()) { 
     arr[index++] = left.front(); 
     left.pop(); 
    } else { 
     arr[index++] = right.front(); 
     right.pop(); 
     ret+=left.size(); 
    } 
    } 

    while(!left.empty()) { arr[index++]=left.front();left.pop(); } 
    while(!right.empty()) { arr[index++]=right.front();right.pop(); } 

    return ret; 
} 

template< class T > 
void mergesortInvCount(T *arr, int beg, int end) { 
    if(beg < end) { 
    int mid = (int)((beg+end)/2); 
    mergesortInvCount(arr, beg, mid); 
    mergesortInvCount(arr, mid+1, end); 
    glob += merge(arr, beg, mid, end); 
    } 
}

對於一些測試情況下，它會產生正確的結果，但對另一些它給了我錯誤的輸出。我是否錯誤地理解了算法，或者我在執行過程中犯了錯誤？有人能幫助我嗎？提前致謝。

Test case: 2 1 3 1 2 
Correct: 4 
Mine: 6

來源

2012-10-10 Rontogiannis Aristofanis

你能不能學會使用調試器-e.g. 'gdb'-來調試你的程序（你可能想用Linux上的'g ++ -Wall -g'編譯它）。 –

你有沒有爲我們提供更具體的錯誤描述（如測試用例和預期的和實際的（不正確的）結果）？ – Grizzly

@Grizzly對不起，編輯。 –

我沒有檢查出你的代碼中的所有步驟，但你行

if(left.front() < right.front())

建議我，在其他分支「RET」是不是隻有當（J）增加>一（i），而且當它們是平等的，這不符合你對案件的描述。因此，也許你應該嘗試改變上面引述入行：

if(left.front() <= right.front())

問候

來源

2012-10-10 19:08:44

測試

if(left.front() < right.front())

應該<=。現在，您從右半部分開始移動相同的值，然後計算不是的倒數（每個這樣的出現計數相同項數左誤寄生倒數）。在你的例子中，你必須複製對，每個創建一個幻像反轉。

來源

2012-10-10 19:02:17

計數在尺寸<code>n</code>的陣列<code>a</code>反轉以陣列C++

回答

相關問題