解題筆記（28）——尋找搗亂分子對

      問題描述：多人排成一個隊列，我們認為從低到高是正确的序列，但是總有部分人不遵守秩序。如果說，前面的人比後面的人高(兩人身高一樣認為是合适的)，那麼我們就認為這兩個人是一對“搗亂分子”，比如說,現在存在一個序列:176, 178, 180, 170, 171

      這些搗亂分子對為<176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>，那麼，現在給出一個整型序列，請找出這些搗亂分子對的個數(僅給出搗亂分子對的數目即可，不用具體的對)

      思路：最簡單的就是用兩層循環，即考察每個元素，檢查該元素後面的元素是否小于它，如果是就找到一個搗亂分子對。複雜度為O(n^2)。這道題的一種改進方案是用分治法，用到了歸并排序的思想。我們可以将數組分成兩部分，總的搗亂分子對為： 前半部分的搗亂分子對 + 後半部分的搗亂分子對 + X，這裡的X為兩部分合并中出現的搗亂分子對，什麼情況下會出現呢？假設前半部分的元素範圍為 A[from] 到A[mid]，後半部分的元素範圍為A[mid + 1] 到A[to]，考慮前半部分的某元素A[i]和後半部分的某元素A[j]，如果A[j] < A[i]，由于兩部分都是排好序的，是以搗亂分子對增加 mid - i + 1個，也就是說A[j]小于A[i], A[i+1].. A[mid]，這個關系顯然成立。

      參考代碼：

int Merge(int *pArray, int from, int mid, int to)
{
	int i = from, j = mid + 1;
	int k = 0, num = 0;
	int *pTmp = new int[to-from+1];
	
	while(i<=mid && j<=to) //歸并排序的主架構
	{
		if(pArray[i] <= pArray[j])
			pTmp[k++] = pArray[i++];
		else
		{
			num += (mid - i + 1);         //增加搗亂分子對
			for(int l = i; l <= mid; l++) //輸出搗亂分子
				cout<<pArray[l]<<' '<<pArray[j]<<endl;

			pTmp[k++] = pArray[j++];
		}
	}
	while(i <= mid) pTmp[k++] = pArray[i++];
	while(j <= to) pTmp[k++] = pArray[j++];

	for(k = from ; k <= to; k++)
		pArray[k] = pTmp[k - from];
	delete [] pTmp;
	return num;
}
int MergeSort(int *pArray, int from, int to)
{
	if(from < to)
	{
		int mid = (from + to) /2;
		int num = MergeSort(pArray, from ,mid) + MergeSort(pArray, mid+1, to); //分别算出兩部分的搗亂分子對
		num += Merge(pArray, from, mid, to);   //合并中出現的搗亂分子對
		return num;
	}
	return 0;
}
           

      本人享有部落格文章的版權，轉載請标明出處 http://blog.csdn.net/wuzhekai1985