2021年10月15日

学习内容：合并两个有序的数组

时间复杂度：O(n)
代码示例（1）

int* MergeTwoArr(int arr[], int len_a, int brr[], int len_b)
{
	if (arr == NULL || brr == NULL)
		return NULL;
	if (len_a <= 0 || len_b <= 0)
		return NULL;
	int* crr = (int*)malloc(sizeof(int) * (len_a + len_b));
	if (crr == NULL) return NULL;
	memset(crr, 0, sizeof(int) * (len_a + len_b));
	int i = len_a - 1;
	int j = len_b - 1;
	int k = len_a + len_b - 1;

	while (i >= 0 && j >= 0)
	{
		if (arr[i] > brr[j])
		{
			crr[k--] = arr[i--];
		}
		else
		{
			crr[k--] = brr[j--];
		}
	}

	while (i >= 0)
	{
		crr[k--] = arr[i--];
	}	
	while (j >= 0)
	{
		crr[k--] = brr[j--];
	}	

	return crr;
}

void Test()
{
	int arr[] = { 1, 3, 5, 7, 9, 11 };
	int brr[] = { 2, 4, 6, 8, 10, 12 };
	int len_a = sizeof(arr) / sizeof(arr[0]);
	int len_b = sizeof(brr) / sizeof(brr[0]);
	int * crr = MergeTwoArr(arr, len_a, brr, len_b);
	for (int i = 0; i < len_a + len_b; i++)
	{
		printf("%d ", crr[i]);
	}
	printf("\n");
}

int main()
{
	Test();
	return 0;
}

运行结果：