數組中的逆序對(劍指offer)

題目描述

在數組中的兩個數字，如果前面一個數字大于後面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數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
           

首先分析題意，對于輸入數組1,2,3,4,5,6,7,0, 逆序對為(1,0),(2,0)…（7,0）一共7個， 即對于數組中的每個數，其可以構成逆序對的個數為它後面且比它小的數的個數， 那麼，最直覺的方法顯然是2層循環，當然，這樣的話時間效率較低，那我們能不能找到更優的方法呢？

對于歸并排序，我們應該都比較熟悉了，那麼這個題目可不可以用歸并排序的思路做呢？ 顯然是可以的。

以上圖為例，我們把數組從中間分成左右2部分，然後分别計算左右2部分的逆序對的個數， 這部分遞歸就OK， 那我們現在的主要目的就是要計算左右2個數組之間的逆序對了， 左右2個數組計算逆序對後我們把他們弄成有序的，那計算2個有序數組之間的逆序對就隻需要O(n)的時間複雜度了， 合并的時候我們需要額外的空間O(n)。

那麼這樣算法的時間複雜度T(n)=2T(n/2)+O(n), 故時間複雜度為O(nlogn)，空間複雜度為O(n).

這樣就很easy了，是不是？ 不說了，直接上代碼

//合并左右2個數組，nums[left:mid]和nums[mid+1:right]
int merge(vector<int>& nums, int left, int mid, int right)
{
	int sum = 0, i = mid, j = right, temp = right - left;
	vector<int> a(right - left + 1, 0);
	//2個有序數組的合并
	while (i >= left && j >= mid + 1)
	{
		if (nums[i]>nums[j])
		{
			a[temp--] = nums[i];
			sum = (sum + j - mid) % 1000000007;
			i--;
		}
		else
		{
			a[temp--] = nums[j];
			j--;
		}
	}
	if (i<left)
	{
		while (j >= mid + 1)
		{
			a[temp--] = nums[j--];
		}
	}
	if (j<mid + 1)
	{
		while (i >= left)
		{
			a[temp--] = nums[i--];
		}
	}
	for (i = left; i <= right; i++)
		nums[i] = a[i - left];
	return sum;
}

//遞歸計算
int mergesort(vector<int>& nums, int left, int right)
{
	if (left == right)
		return 0;
	int mid = (left + right) / 2;
	int leftcnt = mergesort(nums, left, mid) % 1000000007;
	int rightcnt = mergesort(nums, mid + 1, right) % 1000000007;
	return (leftcnt + rightcnt + merge(nums, left, mid, right)) % 1000000007;
}

int InversePairs(vector<int> data) {
	if (data.size() <= 1)
		return 0;
	return mergesort(data, 0, data.size() - 1);
}
           

python 的實作

# -*- coding:utf-8 -*-
class Solution:
    def swap(self, data, i, j):
        temp = data[i]
        data[i] = data[j]
        data[j] = temp
        
    ### 左邊數組為 為data[left]....data[mid]
    ### 右邊數組為 data[data+1]... data[right]
    def merge(self, data, left, mid, right):

        temp = [0 for i in range(right-left+1)]
        i,j = left, mid+1
        k = 0
        res = 0
        while i<mid+1 and j<right+1:
            if data[i] <= data[j]:
                temp[k] = data[i]
                i+= 1
            else:
                temp[k] = data[j]
                res += (mid+1-i)
                j+=1
            k+=1
        if i == mid+1:
            while j<right+1:
                temp[k] = data[j]
                k+=1
                j+=1
        if j == right+1:
            while i<mid+1:
                temp[k] = data[i]
                k+=1
                i+=1
        for i in range(len(temp)):
            data[left+i] = temp[i]
        return res
    
    def mergeSort(self, data, left, right):
        if left >= right:
            return 0
        mid = left + (right-left)/2
        leftCnt = self.mergeSort(data, left, mid)%1000000007
        rightCnt = self.mergeSort(data, mid+1, right)%1000000007
        return ((leftCnt + rightCnt)%1000000007 + self.merge(data, left, mid, right))%1000000007
        
    def InversePairs(self, data):
        # write code here
        if len(data) < 2:
            return 0
        return self.mergeSort(data, 0, len(data)-1)
           

注意python 如何采用切片的方式，像下面這種直接用data的一個子清單并不是他的引用，最後兩個子數組merge 的時候，實際的數組的順序并沒有改變，會報錯

def InversePairs(self, data):
        # write code here
        if len(data) < 2:
            return 0
        if len(data) == 2:
            if data[0] > data[1]:
                self.swap(data, 0, 1)
                return 1
            else:
                return 0
        mid = (len(data)-1)/2
        leftCnt = self.InversePairs(data[0:mid+1])%1000000007
        rightCnt = self.InversePairs(data[mid+1:])%1000000007
        print(data)
        return ((leftCnt + rightCnt)%1000000007 + self.merge(data, mid))%1000000007