효율 적 으로 두 개의 질서 있 는 배열 을 합병 하 다.
두 개의 질서 있 는 배열 을 하나의 질서 있 는 배열 로 합 쳐 첫 번 째 배열 공간 이 두 개의 배열 을 충분히 수용 할 수 있다 고 가정 합 니 다.
분석:
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;
}
요약:
문자열 이 합 쳐 질 때, 우 리 는 뒤에서 이런 사고방식 을 더욱 고려 해 야 한다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.