두 개의 정렬된 배열 병합

질문: 정렬된 배열 A와 B가 있습니다. 배열 A의 남은 공간은 B를 수용하기에 충분합니다. B의 모든 숫자를 A에 삽입하면 모든 숫자가 정렬되는 함수를 구현하십시오. 의.

많은 사람들의 초기 아이디어는 충분히 폭력적인 단순히 삽입하고 A에서 처음부터 끝까지 직접 이동하여 적절한 위치를 찾은 다음 모든 후속 요소를 이동하여 하나의 공간을 만드는 것입니다. 새로 삽입된 숫자를 채우는 것은 가장 비효율적인 방법입니다.

A와 B의 숫자를 끝부터 비교하여 더 큰 숫자를 A의 끝에 복사하는 것이 더 좋은 방법입니다.

문자열의 공백을 "%20"으로 바꾸려는 경우(네트워크 프로그래밍에서 URL에 특수 문자가 포함된 경우)에도 이 솔루션을 적용할 수 있습니다. 공백, "#" 등의 문자는 서버측에서 제대로 해석되지 않을 수 있으므로 변환이 필요합니다. 예를 들어 '%' 뒤에 ASCII 코드의 두 자리 16진수 표현을 추가하는 것입니다. , 공백의 ASCII 코드는 32이므로 16진수 값은 20이며 이는 %20으로 변환됩니다.) 삽입을 위해 처음부터 끝까지 이동하면 문자열이 이동되는 횟수는 입니다. 처음부터 시작하면 문자열에 더 많은 메모리를 적용한 다음 끝부터 복사하고 공백이 나타나면 교체하면 이동 횟수를 효과적으로 줄일 수 있습니다.

배열 병합 코드는 다음과 같습니다.

<?php
/*
$data1 数组A
$data2 数组B
$num1  数组A的有效元素个数
*/
function merge(&$data1,$data2,$num1)
{
	$total=count($data1);
	$num2=count($data2);
	while($num1>0&&$num2>0)
	{
		if($data1[$num1-1]>$data2[$num2-1])
		{
			$data1[$total-1]=$data1[$num1-1];
			$total--;
			$num1--;
		}
		else
		{
			$data1[$total-1]=$data2[$num2-1];
			$total--;
			$num2--;
		}
	}
	if($num2>0)
	{
		while($total>0&&$num2>0)
		{
			$data1[$total-1]=$data2[$num2-1];
			$total--;
			$num2--;
		}
	}
}

$a=array(1,3,5,7,9,0,0,0,0,0);
$b=array(2,4,6,8,10);
merge($a,$b,5);
print_r($a);

저작권 안내 : 이 글은 해당 블로거의 원본 글이므로, 블로거의 허락 없이 복제할 수 없습니다.

위 내용은 관련 측면을 포함하여 두 개의 정렬된 배열을 병합하는 방법을 소개합니다. PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.