【資料結構】課後作業——傳回中位數

P18.11

分别有m，n個整數存放到一位數組A，B中，将兩數組合并并找出合并後數組的中位數。

（1）算法的基本設計思想

建立一個數組，将A，B元素按從小到大的順序放在新數組中，然後傳回。

（2）代碼如下

#include <stdio.h>
#include <malloc.h>
#include <math.h>
unsigned int* array(unsigned int i);//C中不能建立數組元素為變量的數組，該函數用于實作這一功能
void main()
{
	int countA, countB;
	scanf("%d", &countA);
	scanf("%d", &countB);
	unsigned int* A = array(countA);
	unsigned int* B = array(countB);
	unsigned int* AB = array(countA+countB);
	int count;
	printf("請輸入數組一的元素\n");
	for (count = 0; count < countA; count++)
	{
		scanf("%d", &A[count]);
	}
	printf("請輸入數組二的元素\n");
	for (count = 0; count < countB; count++)
	{
		scanf("%d", &B[count]);
	}
	for (count = 0; count < countA; count++)
	{
		printf("%d ", A[count]);
	}
	printf("\n");
	for (count = 0; count < countB; count++)
	{
		printf("%d ", B[count]);
	}
	printf("\n");
	int _countA = 0;
	int _countB = 0;
	for (count = 0; count < countA + countB; count++)
	{
		if (_countA < countA && _countB < countB)
		{
			if (A[_countA] < B[_countB])
			{
				AB[count] = A[_countA];
				_countA++;
			}
			else
			{
				AB[count] = B[_countB];
				_countB++;
			}
		}
		else if (_countA < countA)
		{
			AB[count] = A[_countA];
			_countA++;
		}
		else if (_countB < countB)
		{
			AB[count] = B[_countB];
			_countB++;
		}
		else
			break;
	}
	for (count = 0; count < countA+countB; count++)
	{
		printf("%d ", AB[count]);
	}
	printf("\n");
	int middle;
	middle = AB[(int)floor((double)(countA + countB) / 2)-1];
	printf("中位數為%d", middle);
}
unsigned int* array(unsigned int i)
{
	unsigned int *arr;//指針用于指向數組的首位址
	unsigned int j = 0;
	arr = (unsigned int *)malloc(sizeof(int)*i);//配置設定數組位址空間
	for (j = i; j>0; j--)
		arr[j - 1] = 0;
	return arr;
}
           

（3）複雜度

時間複雜度O(n)

空間複雜度O(n)

較好的算法

（1）算法的基本設計思想

我們考慮中位數的定義，即該數字前面和後面各有一半的數字。設兩有序數組為A,B，長度均為n,中位數為a，b。那麼在數組A中有一半比a大，一半比a小。數組b也一樣。對于合并後的數組AB，有n個數比中位數ab大，有n個數比ab小。那麼，如果我們能不斷從A,B中删去元素，使得這個n值不斷變小，最後為0，那麼剩下的數就是中位數。

考慮合并後數組的中位數出現的範圍。因為A，B都是有序的數組，那麼對于a,b，有以下幾種情況：

A1 a A2

B1 b B2

AB1 ab AB2

• a>b：這種情況下說明B1中的元素必定在AB1中，A2中的元素必定在AB2中，這兩部分都可以舍去。
• a<b：這種情況下說明A1中的元素必定在AB1中，B2中的元素必定在AB2中，這兩部分都可以舍去。
• a=b：這種情況下說明a和b就是中位數。
• 注意每次舍棄的都應該是相等的長度。

第一次舍去後可得到兩個新的數組，再次使用直到兩數組中均隻剩一個元素，那麼剩下的兩個中的較小的就是所求的中位數。

（2）代碼如下

#include <stdio.h>
#include <malloc.h>
#include <math.h>
unsigned int* array(unsigned int i);//C中不能建立數組元素為變量的數組，該函數用于實作這一功能
void main()
{
	int countA, countB;
	scanf("%d", &countA);
	scanf("%d", &countB);
	unsigned int* A = array(countA);
	unsigned int* B = array(countB);
	//unsigned int* AB = array(countA+countB);
	int count;
	printf("請輸入數組一的元素\n");
	for (count = 0; count < countA; count++)
	{
		scanf("%d", &A[count]);
 	}
	printf("請輸入數組二的元素\n");
	for (count = 0; count < countB; count++)
	{
		scanf("%d", &B[count]);
	}
	for (count = 0; count < countA; count++)
	{
		printf("%d ", A[count]);
	}
	printf("\n");
	for (count = 0; count < countB; count++)
	{
		printf("%d ", B[count]);
	}
	printf("\n");
	int _countA1 = 0;
	int _countB1 = 0;
	int _countA2 = countA-1;
	int _countB2 = countB-1;
	int middleA;
	int middleB;
	int middle = 0;
	int mA, mB;
	while (_countA1 != _countA2)
	{
		mA = (int)floor((double)(_countA1 + _countA2) / 2);
		middleA = A[mA];
		mB = (int)floor((double)(_countB1 + _countB2) / 2);
		middleB = B[mB];
		if (middleA == middleB)
		{
			middle = middleA;
			break;
		}
		else if (middleA > middleB)
		{
			if ((_countA1 + _countA2) % 2 == 0)
			{
				_countB1 = mB;
				_countA2 = mA;
			}
			else
			{
				_countB1 = mB + 1;
				_countA2 = mA;
			}
		}
		else
		{
			if ((_countA1 + _countA2) % 2 == 0)
			{
				_countB2 = mB;
				_countA1 = mA;
			}
			else
			{
				_countB2 = mB;
				_countA1 = mA + 1;
			}
		}
	}
	if (middle != 0)
		printf("中位數為%d", middle);
	else
	{
		mA = (int)floor((double)(_countA1 + _countA2) / 2);
		middleA = A[mA];
		mB = (int)floor((double)(_countB1 + _countB2) / 2);
		middleB = B[mB];
		printf("中位數為%d", middleA < middleB ? middleA : middleB);
	}	
}
unsigned int* array(unsigned int i)
{
	unsigned int *arr;//指針用于指向數組的首位址
	unsigned int j = 0;
	arr = (unsigned int *)malloc(sizeof(int)*i);//配置設定數組位址空間
	for (j = i; j>0; j--)
		arr[j - 1] = 0;
	return arr;
}
           

（3）複雜度

時間複雜度O(logn)

空間複雜度O(1)