題目描述
在數(shù)組中的兩個(gè)數(shù)字，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)?。輸入一個(gè)數(shù)組,求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對(duì)1000000007取模的結(jié)果輸出。 即輸出P%1000000007
解題思路
暴力解法
順序掃描整個(gè)數(shù)組，每掃描到一個(gè)數(shù)字的時(shí)候，逐個(gè)比較該數(shù)字和它后面的數(shù)字的大小。如果后面的數(shù)字比它小，則這兩個(gè)數(shù)字就組成一個(gè)逆序?qū)Α＜僭O(shè)數(shù)組中含有n個(gè)數(shù)字，由于每個(gè)數(shù)字都要和O(n)個(gè)數(shù)字作比較，因此這個(gè)算法的時(shí)間復(fù)雜度是O(n2)。
分治思想
采用歸并排序的思路來(lái)處理，如下圖，先分后治
先把數(shù)組分解成兩個(gè)長(zhǎng)度為2的子數(shù)組，再把這兩個(gè)子數(shù)組分解成兩個(gè)長(zhǎng)度為1的子數(shù)組。接下來(lái)一邊合并相鄰的子數(shù)組，一邊統(tǒng)計(jì)逆序?qū)Φ臄?shù)目。在第一對(duì)長(zhǎng)度為1的子數(shù)組{7}、{5}中7>5，因此（7,5）組成一個(gè)逆序?qū)?。同樣在第二?duì)長(zhǎng)度為1的子數(shù)組{6}，{4}中也有逆序?qū)Γ?,4），由于已經(jīng)統(tǒng)計(jì)了這兩對(duì)子數(shù)組內(nèi)部的逆序?qū)Γ虼诵枰堰@兩對(duì)子數(shù)組進(jìn)行排序，避免在之后的統(tǒng)計(jì)過(guò)程中重復(fù)統(tǒng)計(jì)。
逆序?qū)Φ目倲?shù)=左邊數(shù)組中的逆序?qū)Φ臄?shù)量+右邊數(shù)組中逆序?qū)Φ臄?shù)量+左右結(jié)合成新的順序數(shù)組時(shí)中出現(xiàn)的逆序?qū)Φ臄?shù)量；
總結(jié)統(tǒng)計(jì)數(shù)組逆序?qū)Φ倪^(guò)程：先把數(shù)組分隔成子數(shù)組，先統(tǒng)計(jì)出子數(shù)組內(nèi)部的逆序?qū)Φ臄?shù)目，然后再統(tǒng)計(jì)出兩個(gè)相鄰子數(shù)組之間的逆序?qū)Φ臄?shù)目。在統(tǒng)計(jì)逆序?qū)Φ倪^(guò)程中，還需要對(duì)數(shù)組進(jìn)行排序，其實(shí)這個(gè)排序過(guò)程就是歸并排序的思路。
代碼實(shí)現(xiàn)
private long cnt = 0;
private int[] tmp; // 在這里聲明輔助數(shù)組，而不是在 merge() 遞歸函數(shù)中聲明
public int InversePairs(int[] nums) {
tmp = new int[nums.length];
mergeSort(nums, 0, nums.length - 1);
return (int) (cnt % 1000000007);
}
private void mergeSort(int[] nums, int l, int h) {
if (h - l < 1)
return;
int m = l + (h - l) / 2;
mergeSort(nums, l, m);
mergeSort(nums, m + 1, h);
merge(nums, l, m, h);
}
private void merge(int[] nums, int l, int m, int h) {
int i = l, j = m + 1, k = l;
while (i <= m || j <= h) {
if (i > m)
tmp[k] = nums[j++];
else if (j > h)
tmp[k] = nums[i++];
else if (nums[i] < nums[j])
tmp[k] = nums[i++];
else {
tmp[k] = nums[j++];
this.cnt += m - i + 1; // nums[i] >= nums[j]，說(shuō)明 nums[i...mid] 都大于 nums[j]
}
k++;
}
for (k = l; k <= h; k++)
nums[k] = tmp[k];
}
