효율 적 으로 두 개의 질서 있 는 배열 을 합병 하 다.

1296 단어 알고리즘null
질문:
두 개의 질서 있 는 배열 을 하나의 질서 있 는 배열 로 합 쳐 첫 번 째 배열 공간 이 두 개의 배열 을 충분히 수용 할 수 있다 고 가정 합 니 다.
분석:
a 배열 이 매우 크다 는 것 을 감안 하여 a 배열 에서 직접 합병 할 수 있 지만 효율 을 중시 해 야 한다.단순히 이전 이후 에 합병 하면 효율 이 매우 낮 을 것 이다. 왜냐하면 a 배열 뒤의 숫자 는 끊임없이 이동 해 야 하기 때문이다.다른 방향 으로 바 꾸 면 우 리 는 뒤에서 앞으로 합병 하고 먼저 총 길 이 를 계산 하 며 지침 을 설정 하여 a 배열 에서 마지막 으로 앞으로 이동 합 니 다.
알고리즘 코드:
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define MAX 1024

void combine(int *a, int *b, int len1, int len2)
{
	if(a == NULL || b == NULL || (len1 + len2) > MAX)
		return ;

	int new_point;
	int a_point = len1 - 1;
	int b_point = len2 - 1;

	new_point = len1 + len2 -1;	//    

	while(a_point >= 0 && b_point >= 0)
	{
		if(a[a_point] > b[b_point])
		{
			a[new_point--] = a[a_point--];
		}
		else
		{
			a[new_point--] = b[b_point--];
		}
	}

	while(a_point >= 0)
	{
		a[new_point--] = a[a_point--];
	}

	while(b_point >= 0)
	{
		a[new_point--] = b[b_point--];
	}

	return ;
}

int main()
{
	int b[MAX] = {1,2,3,4};
	int a[MAX] = {5,6,7,8};

	combine(a, b, 4, 4);

	for(int i =0 ; i <= 4 + 4 -1; i++)
	{
		cout << a[i] << " ";
	}

	return 0;
}

요약:
문자열 이 합 쳐 질 때, 우 리 는 뒤에서 이런 사고방식 을 더욱 고려 해 야 한다.

좋은 웹페이지 즐겨찾기