劍指offer 陣列中的逆序對

2022-11-24 15:21:41 字數 1219 閱讀 5586

在陣列中的兩個數字,如果前面一個數字大於後面的數字,則這兩個數字組成一個逆序對。輸入一個陣列,求出這個陣列中的逆序對的總數p。並將p對1000000007取模的結果輸出。 即輸出p%1000000007

題目保證輸入的陣列中沒有的相同的數字

資料範圍:

對於%50的資料,size<=10^4

對於%75的資料,size<=10^5

對於%100的資料,size<=2*10^5

示例1

1,2,3,4,5,6,7,0

7

思路:一、暴力求解法,兩個for迴圈;二、歸併排序的過程中記錄逆序對數

1

class

solution

8private:9

//需要注意的地方在於容易溢位,所以直接用long long最保險,

10//

如果用int,需要經常判斷逆序數有沒有溢位。

11long

long mergecount(vector &data, vector ©, int l, int

r) 16

int mid = (r - l) / 2 + l; //

不推薦 (r + l)/ 2,因為r + l容易溢位.

17//

int mid = (r + l) >> 1;

18//

排序陣列左右兩部分

19long

long lcount =mergecount(data, copy, l, mid);

20long

long rcount = mergecount(data, copy, mid + 1

, r);

21int i = l, j = mid + 1, index =l;

22long

long count = 0;23

//歸併左右排序好兩個子陣列a和b,同時記錄逆序對數

24while ((i <= mid) && (j <=r)) else31}

32while (i <=mid)

35while (j <=r)

38for(int k = l; k <=r; ++k)

39 data[k] =copy[k];

40return (lcount + rcount + count) % 1000000007;41

}42 };

劍指offer 陣列中的逆序對

劍指 offer 51.陣列中的逆序對 在陣列中的兩個數字,如果前面一個數字大於後面的數字,則這兩個數字組成一個逆序對。輸入一個陣列,求出這個陣列中的逆序對的總數。示例 1 輸入 7,5,6,4 輸出 5 限制 0 陣列長度 50000 import org.junit.jupiter.api.te...

劍指Offer 35 陣列中的逆序對

思路 看到這樣的題目,最簡單的想法就是遍歷每一個元素,讓其與後面的元素對比,如果大於則count 但是這樣的時間複雜度是o n2 根據題目給出的資料量,很明顯超時。因此想到了用歸併排序的思想。1 class solution 13else 1419 20 while i mid temp k dat...

劍指 Offer 51 陣列中的逆序對

在陣列中的兩個數字,如果前面一個數字大於後面的數字,則這兩個數字組成一個逆序對。輸入一個陣列,求出這個陣列中的逆序對的總數。示例1 輸入 7,5,6,4 輸出 5限制 0 陣列長度 50000 假設給定陣列為 8,10,15,20,70,9,25,50,60,100 這個陣列的前一半和後一半都是有序...