|
|
Posted by Bob Stearns on 12/15/06 06:02
laredotornado@zipmail.com wrote:
> Hi,
>
> I'm using PHP 4.4.4. Let's say I have two scalars, $list1 and $list2.
> Both are comma separated lists of ordered, unsigned, unique integers.
> An example would be
>
> $list1 = "2,26,345";
> $list2 = "3,4,26,35,525";
>
> I am wondering if there is a short way of determining if all the
> numbers in $list1 occur in $list2.
>
> Grateful for any advice. Thanks, - Dave
>
If, as in your example, the two lists are sorted, it can be done in
O(n+m) time by doing stepped compare. If they are unsorted, it can also
be done in O(n+m) time (with a much bigger constant factor) by making
the second list into the subscripts of an array, then checking for the
existence of the first list's elements in the new array.
Sample code (untested):
$i1 = 0;
$i2 = 0;
while($i1<count($list1) && $i2<count($list2)) {
if($list2[$i2]==$list1[$i1]) {
$i1++;
$i2++;
}
elseif($list2[$i2]<$list1[$i1]) {
$i2++;
}
else { /* this the failure case */ }
$fail = TRUE;
break;
}
}
for($i2==0; $i2<count($list2); $i2++) {
$test[$list2[$i2]] = TRUE;
}
for($i1==0; $i1<count($list1); $i1++) {
if(!array_key_exists($list1[$i1],$test) {
$fail = TRUE;
break;
}
}
We use these techniques rather than the much easier to code in_array()
because the time for this technique in O(m*n) since $list2 must be
searched completely for each element of $list1.
Navigation:
[Reply to this message]
|