PHP 从数组中查找最小的k个元素

答案

思路：

  • 假设最前面的1000个数为最小的，算出这1000个数中最大的数，然后和第1001个数比较

  • 如果这个最大的数比第1001个数小的话，跳过

  • 如果这个最大的数比第1001个数大则将两个数交换位置，并算出新的1000个数里面的最大数

  • 再和下一个数比较，以此类推

  1. /**
  2.  * 从数组里找出最小的 $k 个数
  3.  * @param $arr array 输入数组
  4.  * @param $k int 输出元素个数
  5.  * @return array 最小元素集合
  6.  */
  7. function getMinK($arr, $k)
  8. {
  9.     $n = count($arr);
  10.     $minArray = array();
  12.     for ($i = 0; $i < $n; $i++) {
  13.         if ($i < $k) {
  14.             $minArray[$i] = $arr[$i];
  15.         } else {
  16.             if ($i == $k) {
  17.                 $maxPos = getMaxPos($minArray);
  18.                 $max = $minArray[$maxPos];
  19.             }
  20.             if ($arr[$i] < $max) {
  21.                 $minArray[$maxPos] = $arr[$i];
  22.                 $maxPos = getMaxPos($minArray);
  23.                 $max = $minArray[$maxPos];
  24.             }
  25.         }
  26.     }
  28.     return $minArray;
  29. }
  31. /**
  32.  * 从数组中查找最大值的位置
  33.  * @param $arr array 待查找数组
  34.  * @return int 位置
  35.  */
  36. function getMaxPos($arr)
  37. {
  38.     $pos = 0;
  39.     for ($i = 1; $i < count($arr); $i++) {
  40.         if ($arr[$i] > $arr[$pos]) {
  41.             $pos = $i;
  42.         }
  43.     }
  45.     return $pos;
  46. }

测试代码：

  1. $arr = [1, 100, 20, 22, 33, 44, 55, 66, 23, 79, 18, 20, 11, 9, 129, 399, 145, 2469, 58];
  2. $res = getMinK($arr, 5);
  4. // 输出：[1,9,20,11,18]
  5. echo json_encode($res);