資料結構——順序表習題解(II)

本題目來自王道考研教材，結合答案給出個人的一些寫法，
1.【統考真題】一個長度為L的升序序列S，處在第L/2上取整的數字稱之為它的中位數，例如，若序列S1=(11,13,15,17,19),則S1的中位數為15，兩個序列的中位數是他們所有的元素組成的升序序列的中位數，例如，若S2=(2,4,6,8,20)則S1，S2的中位數是11，現在有兩個等長升序序列A，B，試求一個在時間和空間兩方面盡可能高效的演算法，找出A和B的中位數，要求：
1）給出演算法的基本思想
2）寫出代碼，關鍵之處給出注釋
3）說明此演算法的時間復雜度和空間復雜度
難度：適中：定理的證明較難想到，O(logn)的演算法不好想，需要對中位數的性質和概念有較深刻的理解，
思想：
若用歸并排序，則一定時間復雜度較高，本體應該采用減治法的思想：
設序列A的中位數為am，序列B的中位數為bm
定理1：A和B的中位數cm大小一定介于am和bm之間
簡要證明：由中位數定義，假設A和B中有n個數字（為了方便這里設n為奇數，偶數證明同理），則必然有(n-1)/2個數小于等于am,有(n-1)/2個數大于等于bm，
則分析一下：
1.若am=bm時，則中位數必然為am(或者說bm),因為此時必然有（n-1)個數字小于等于am，有（n-1)個數字大于等于am,am必然為中位數，
2.若am<bm(am>bm同理）：若此時cm<am,則必然有cm<am<bm,則此時必然有不包含bm的（n-1)/2個數大于等于bm,也有不包含am在內的（n-1)/2個數大于等于am，則必然至少有2*（n-1)/2+1+1個數字大于cm,即至少有(n+1)個數字大于cm,則cm必不可能為中位數，

由上述證明我們思考一下怎么做最快：
我們取A的中位數am,B的中位數bm,由上述定理可知，AB的中位數一定介于am和bm之間，若此時
1.am=bm，由中位數定義，am即為中位數
2.am<bm, 則我們可以舍棄am之前的數字和bm之后的數字（兩邊舍棄的數量必須相等），這樣能保證大于中位數和小于中位數的數字個數相等，然后再舍棄數字后的新陣列A’ B’中繼續進行這一操作，直到出現1中條件或者兩陣列都只剩一個元素為止，由定義，這時候取較小的那個元素即可，
3.am>bm,同理
此演算法每次將陣列規模縮減一半，所以時間復雜度O(logn) 空間復雜度O(1)

#include <iostream>
using namespace std;
int findMid(int *a, int *b, int n)
{
	int s1 = 0, s2 = 0, d1 = n - 1, d2 = n - 1;
	//用s表示首指標，d表示尾指標，
	while (s1 != d1 || s2 != d2) 
	{
		int mid1 = (s1 + d1) / 2;
		int mid2 = (s2 + d2) / 2;
		if (a[mid1] == b[mid2]) return a[mid1];
		if (a[mid1] < b[mid2])
		{
			if ((d1 - s1+1) % 2 == 0)//當序列個數為偶數個時
			{
				s1 = mid1 + 1;
				d2 = mid2;
			}
			else//序列個數為奇數個時
			{
				s1 = mid1;
				d2 = mid2;
			}
		}
		else
		{
			if ((d2 - s2 + 1) % 2 == 0)
			{
				s2 = mid2 + 1;
				d1 = mid1;
			}
			else
			{
				s2 = mid2;
				d1 = mid1;
			}
		}
	}
	return a[s1] < b[s2] ? a[s1] : b[s2];
}
//測驗代碼
int main()
{
	int a[] = { 11,13,15,17,19 };
	int b[] = { 2,4,6,8,20 };
	int mid = findMid(a,b,5);
	cout << "中位數為:" << mid;

}

2.【統考真題】已知一個整數序列A=(a0,a1,…an-1) 其中0<=ai<n(0<=i<n) 若存在ap1=ap2=…=apm=x 且m>n/2,則稱x為A的主元素，例如A=（0，5，5，3，5，7，5，5）則5為主元素，又如A=(0,5,5,3,5,1,5,7)則A中沒有主元素，假設A中的n個元素保存在一個一維陣列中，請設計一個盡可能高效的演算法，求出A的主元素，若存在主元素，回傳這個元素，若不存在主元素，回傳-1.

難度：較難，考場上不推薦花太多時間思考最佳演算法，寫個快排然后統計倒是不錯的選擇，
思路：無非是求最大重復元素個數，并進行一個判斷，如果直接從前往后進行掃描每個元素出現的位置，則會達到O(n2)的時間復雜度，顯然不是一個好的做法，若排序后統計，也至少有O(nlogn)的時間復雜度，
我們思考如下問題：
1.主元素必定唯一：因為m>n/2,剩下的重復元素的個數必然小于n/2,也就是說剩下的元素個數必然少于主元素個數，
思路:
陣列中存在主元素時，所有的非主元素的個數和必少于一半，如果讓主元素與一個非主元素“配對”，則最后多出來的元素（沒有元素與之配對）就是主元素，但如何知道哪個元素是主元素呢？不知道主元素是誰，又如何進行“配對”呢？這無妨，從前向后掃描陣列元素，假定遇到的當前值選定為主元素，再次遇到它時，計數加1，遇到與它不等的值時，計數減1，當計數減為0后，將遇到的下一個值重新選定為主元素，掃描完畢，當前選定的元素（計數值大于0）可能是主元素，但未必一定是主元素，還需要對陣列再進行一次掃描，記錄它出現的實際個數，以判定它是否是主元素，
演算法可分為以下兩步：

① 選取候選的主元素：依次掃描所給陣列中的每個整數，將第一個遇到的整數Num保存到c中，記錄Num的出現次數為1；若遇到的下一個整數仍等于Num，則計數加1，否則計數減1；當計數減到0時，將遇到的下一個整數保存到c中，計數重新記為1，開始新一輪計數，即從當前位置開始重復上述程序，直到掃描完全部陣列元素，

② 判斷c中元素是否是真正的主元素：再次掃描該陣列，統計c中元素出現的次數，若大于n/2，則為主元素，否則，序列中不存在主元素，

int Majority ( int A[], int n )
{     int i, c, count = 1; // c用來保存候選主元素，count用來計數
      c= A[0]; //設定A[0]為候選主元素
      for( i = 1; i < n; i++ ) // 查找候選主元素
        if( A[i] == c )  count++;   // 對A中的候選主元素計數
           else
               if( count > 0 ) 
               count--;  // 處理不是候選主元素的情況
                    else{         // 更換候選主元素，重新計數
                     c= A[i];
                     count= 1;
                         }
            if( count > 0 )
               for( i = 0,count = 0; i < n; i++ )    // 統計候選主元素的實際出現次數
                         if ( A[i] == c )  
                         count++;
            if( count > n/2 )  
              return c;   // 確認候選主元素
             else  return -1;     //不存在主元素
}

3.【統考真題】給定一個含n(n>1)個整數的陣列，請設計一個時間和空間上盡可能高效的演算法，找出陣列中未出現的最小的正整數，例如，陣列{-5，3，2，3}中未出現的最小正整數為1，{1，2，3}中未出現的最小正整數為4
思路：我們采用空間換時間的做法，再申請一個n維陣列B,B表示前n個正整數的出現情況，初值設為0，然后掃描A中陣列，若ai>n或ai<=0,則未出現的最小正整數必然在b中，若1<ai<=n,則在B的對應位置上置換為1，表示這個數字已經出現過了，若掃描完陣列B滿，則證明陣列A涵蓋了1-n，且每個只出現了一次，那么未出現的最小整數必然為(n+1）

#include <iostream>
using namespace std;
int FindMin(int* a, int n)
{
	int i = 0;
	int* b;
	b = (int*)malloc(sizeof(int) * n);
	memset(b, 0, sizeof(int) * n);
	for (int i = 0; i < n; i++)
	{
		if (a[i] > 0 && a[i] <= n)
		{
			b[a[i] - 1] = 1;
		}
	}
	for  (i = 0; i < n; i++)
	{
		if (b[i] == 0)
			break;
	}
	return i + 1;
}
int main()
{
	int a[] = { -5,3,2,3 };
	int min = FindMin(a, 4);
	cout << "此陣列中未出現的最小正整數為" << min;

}