1

真正寻找解决方案（我知道有人问过类似的问题）并试图用“英语”理解如何思考代码。

我想在给定某个数字的数组中找到最接近的数字；下面的代码是我迄今为止所拥有的。

//Array of numbers
$haystack = array(1,4,67,34,12,76,6,8,45,2);

//Number which we are finding the closest
$needle = 4;

sort($haystack);

foreach($haystack as $number){
    if($number > $needle){
        $difference = array($number-$needle);
        $smallest_num = array_shift($difference);
        echo $smallest_num.", "; //Echos out 2, 4, 8, 30, 41, 63, 72,
    }
}

先谢谢了。

4

4 回答 4

0

对于这种情况，二分搜索看起来是个不错的选择。

它比这要复杂一些（例如，您拥有1,5,6并且正在寻找4。您查看 5 并取左半边，即 1。这意味着您必须返回并取 5，因为它更接近），但是您应该能够将其用作基本算法。

于 2013-03-15T01:14:55.933 回答
0

这是我想出的一个小函数，usort用于返回整个 Haystack，按与 Needle 的接近程度排序。我在函数之后提供的示例应该 echo 77。（对不起，如果评论有点过分，我喜欢我的文档是防白痴的。）

// Sorts the array by closest to given number
function Find_Closest($Haystack, $Needle)
{
    $GLOBALS['Needle'] = $Needle; // allows $Needle to be accessible inside Compare()
    // Comparison function used by usort() to determine which number is closest to the needle
    if(!function_exists('Reviews_By_Date_Published')) // Only declare function if it hasn't already been declared
    {
        function Compare($A, $B)
        {
            global $Needle;
            $DistanceB = abs($B - $Needle);
            $DistanceA = abs($A - $Needle);
            return($DistanceA - $DistanceB);
        }
    }
    usort($Haystack, 'Compare'); // Sorts the Haystack by closest to Needle, using Compare()
    return $Haystack;
}

    // Example:
    $ArrayInQuestion = array(3,4,8,3,6,77,3,5,85,1,24,3);
    $SortedArray = Find_Closest($ArrayInQuestion, 76);
    $Closest = $SortedArray[0];
    echo "Closest = $Closest";

请注意，我的函数假定数组实际上是数组而不是其他数据类型。

于 2013-03-17T01:03:51.173 回答
0

我想出的最简单的函数（它不断拆分数组，直到它上下到达最接近的数字$needle，然后最后比较两者。

function findClosest($needle, array $haystack) {

    sort($haystack);

    $b = 0; // bottom
    $u = count($haystack) - 1; // up

    while ($u - $b > 1) {
        $m = round(($b + $u) / 2);
        if ($haystack[$m] < $needle) $b = $m;
        else $u = $m;
    }

    $x = $haystack[$b];
    $y = $haystack[$u];
    return (($needle-$x) > ($y-$needle)) ? $y : $x;

}

如何在数组中减少数组索引的示例：

$needle = 7;
$array = array(2, 4, 8, 30, 41, 63, 72);

# loop: [$b..$u]

1 loop: [0..6]
2 loop: [0..3]
3 loop: [0..2]
4 loop: [1..2]

现在我们知道$haystack[1]is just below$needle和$haystack[2]is above $needle。然后脚本将进行此评估：

return (7-4 > 8-7) ? 8 : 4;

返回正确的结果：8。

于 2013-03-15T01:32:27.673 回答
-1

I've found a solution in PHPs docs using the levenshtein function. By slightly altering the example code, I got it to find the closest number in a sorted array. The function is also relatively quick compared to other similar PHP functions.

<?php
function findClosest($input = 0){
    // array of numbers to check against
    $numbers  = array(4,7,10,15,
                    1,2,666,1234);
    sort($numbers);
    // no shortest distance found, yet
    $shortest = -1;

    // loop through numbers to find the closest
    foreach ($numbers as $num) {

        // calculate the distance between the input num,
        // and the current num
        $lev = levenshtein($input, $num);

        // check for an exact match
        if ($lev == 0) {

            // closest num is this one (exact match)
            $closest = $num;
            $shortest = 0;

            // break out of the loop; we've found an exact match
            break;
        }

        // if this distance is less than the next found shortest
        // distance, OR if a next shortest num has not yet been found
        if ($lev <= $shortest || $shortest < 0) {
            // set the closest match, and shortest distance
            $closest  = $num;
            $shortest = $lev;
        }
    }
    echo "Closest number is: " . $closest;
 }
?>

I hope this helps, Adam.

于 2013-03-15T02:09:51.817 回答