php - 如何确定数组中比其他数字更接近的两个数字

Question

我有这个数组:

$arr = array (20, 1, 5, 10, 7, 16);

我想得到 5 和 7。因为这些比其他项目更接近彼此。换句话说，它们之间的区别是最小的数字:

7 - 5 = 2 // 2 is lowest number as the difference between all array's items

我该怎么做？

---

$keep = $arr[0];
$diff = $arr[1] - $arr[0];
foreach ($arr as $item) {
    if ( ($keep - $item) < $diff && $keep != $item ) {
        $diff = $item;
    }
}

我的代码不完整，因为它只是将第一项与其他项进行比较。

Answer 1

说明

因此，要获得数组中彼此最接近的两个数字，您必须将每个值与其他值进行比较。但是您不必将它们与它们自己进行比较，也不必与您之前已经比较过的那些进行比较。

要计算需要进行多少次比较，可以使用 binomial coefficient :

(n)            n!
(k)   →   ─────────────
          k! * (n - k)!

_{其中 n 是元素的总数，k 是你选择的数量}

在您的示例中，这意味着:

n = 6 //Array elements
k = 2 //Two values which you compare

     6!                  720
─────────────   →   ─────────────   = 15 comparison
2! * (6 - 2)!          2  *  24

可视化

20 , 1 , 5 , 10 , 7 , 16  //Array values
↓    ↑   ↑   ↑    ↑   ↑
└────┴───┴───┴────┴───┘  //20 compared to all values, except itself
     ↓   ↑   ↑    ↑   ↑
     └───┴───┴────┴───┘  //1  compared to all values, except itself + [20]
         ↓   ↑    ↑   ↑
         └───┴────┴───┘  //5  compared to all values, except itself + [20, 1]
             ↓    ↑   ↑
             └────┴───┘  //10 compared to all values, except itself + [20, 1, 5]
                  ↓   ↑
                  └───┘  //7  compared to all values, except itself + [20, 1, 5, 10]

                         //16 compared to all values, except itself + [20, 1, 5, 10, 7]

现在要在代码中执行此操作，我们需要 2 个循环来为第一个循环的每个值遍历整个数组。但正如我们已经说过的，我们可以忽略值本身和之前的值，因此为此我们使用 2 个 for 循环并将内循环的键设置为外键 + 1。

for($key = 0, $length = count($arr); $key < $length; $key++){          
    for(<b>$innerKey = $key + 1</b>; $innerKey < $length; $innerKey++){
      //↑ Skipping the previous values and the value itself    
    }               
}

在内部循环本身中，我们只需要访问外部循环的当前值并获得与内部循环值相比的差异。这也适用于负数，我们只是将其包装到 abs() 调用中，以使差值始终为正数。

然后我们只检查差异是否小于我们已经找到的最小差异，保存在 $nearest 中。 (我们初始化$nearest为数组最大和最小值之差+1):

if( ($diff = abs($arr[$keys[$key]] - $arr[$keys[$innerKey]])) < $nearest)          

如果差异小于我们已经找到的最小差异，我们将这两个值写入一个数组并设置新的最小差异:

$result = [$arr[$keys[$key]], $arr[$keys[$innerKey]]];
$nearest = $diff;

代码

<?php

    $arr = [20, 1, 5, 10, 7, 16];

    $keys = array_keys($arr);
    $nearest = max($arr) - min($arr) + 1;
    $result = [];

    for($key = 0, $length = count($arr); $key < $length; $key++){

        for($innerKey = $key + 1; $innerKey < $length; $innerKey++){

            if( ($diff = abs($arr[$keys[$key]] - $arr[$keys[$innerKey]])) < $nearest){
                $result = [$arr[$keys[$key]], $arr[$keys[$innerKey]]];
                $nearest = $diff;

            }

        }

    }

    print_r($result);

?>

输出

[5, 7]