計算倒數的數目

-2

讓A[1...n]是一個由n個不同數字組成的數組。計算倒數的數目

該對(i, j)稱爲逆，如果i < j and A [i] > A [j]。

實施例：

甲：=（2，3，8,6，1）=> A具有5個逆。

任務：

寫程序找到序列A [1..N]，使得算法的複雜度是O（n * logn）時間的倒數的數。

歡迎堆棧溢出！家庭作業問題應該顯示你的努力和當前的代碼。逐字地拋棄作業問題不可能得到很好的迴應;解釋你在苦苦掙扎，並提供清晰的調試信息。 – Aurora0001

http://stackoverflow.com/a/40001355/1040597 – Tempux

此問題可以基於合併排序來解決。

嚴格來說，您應該修改程序merge(A, B)，它返回的配對數(a, b) such that a in A, b in B and b > c。

正如你可以看到，是解決這一問題所需的運行時間是合併排序的運行時間，因此O(n * log(n))

2016-10-22 17:22:32

我試過了，但事實並非如此。你可以幫我編碼 –

你可以發佈你的代碼，我可以指導你通過解決方案的路徑 –

回答