ソートされた 2 つの配列をマージする

質問: 2 つのソートされた配列 A と B があります。配列 A の残りのスペースは、B を収容するのにちょうど十分です。B のすべての数値を A に挿入し、すべての数値がソートされる関数を実装してください。

多くの人の最初のアイデアは単純に挿入することですが、これは十分に暴力的です。適切な位置を見つけたら、次のすべての要素を移動して、少しのスペースを埋めます。この種のアプローチは最も効率的ではありません。

逆を行うよりも、A と B の数値を末尾から比較し、大きい方の数値を A の末尾にコピーする方が良い方法です。

この解決策は、文字列内のスペースを「%20」に置き換える場合にも適用できます (ネットワーク プログラミングでは、URL にスペースや「#」などが含まれる場合があります)。サーバー側で正しく解析されないため、変換する必要があります。変換ルールは、「%」の後に ASCII コードの 2 桁の 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);

著作権表示: この記事はブロガーによるオリジナルの記事であり、ブロガーの許可なく複製することはできません。

上記は、内容の側面も含めて 2 つの順序付けされた配列のマージを紹介しています。PHP チュートリアルに興味のある友人に役立つことを願っています。