Maison > développement back-end > tutoriel php > 合并两个有序数组

合并两个有序数组

WBOY
Libérer: 2016-08-08 09:22:05
original
1004 Les gens l'ont consulté

题目:有两个排序的数组A和B,数组A剩余的空间刚好够容纳B,请实现一个函数,把B中的所有数字插入到A中并且所有的数都是排序的。

很多人一开始的想法就是简单的插入,足够暴力,在A中直接从头到尾遍历,找到合适的位置就移动后面所有的元素,让出一个位填补新插入的数,这种做法是效率最低的。

反其道而行之,更好的办法是从尾开始比较A和B中的数字,把较大的数字复制到A的末尾。

这种解决方法同样可以运用到字符串替换中去,如果要将字符串中的空格替换成“%20”(在网络编程中,URL中如果包含空格、“#”等特殊字符,可能导致在服务器端无法正确解析,所以需要进行转换,转换规则为在‘%’后面加上ASCII码的两位十六进制表示。比如空格的ASCII码是32,所以十六进制就是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);
Copier après la connexion

版权声明:本文为博主原创文章,未经博主允许不得转载。

以上就介绍了合并两个有序数组,包括了方面的内容,希望对PHP教程有兴趣的朋友有所帮助。

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal