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();
  11. for ($i = 0; $i < $n; $i++) {
  12. if ($i < $k) {
  13. $minArray[$i] = $arr[$i];
  14. } else {
  15. if ($i == $k) {
  16. $maxPos = getMaxPos($minArray);
  17. $max = $minArray[$maxPos];
  18. }
  19. if ($arr[$i] < $max) {
  20. $minArray[$maxPos] = $arr[$i];
  21. $maxPos = getMaxPos($minArray);
  22. $max = $minArray[$maxPos];
  23. }
  24. }
  25. }
  26. return $minArray;
  27. }
  28. /**
  29. * 从数组中查找最大值的位置
  30. * @param $arr array 待查找数组
  31. * @return int 位置
  32. */
  33. function getMaxPos($arr)
  34. {
  35. $pos = 0;
  36. for ($i = 1; $i < count($arr); $i++) {
  37. if ($arr[$i] > $arr[$pos]) {
  38. $pos = $i;
  39. }
  40. }
  41. return $pos;
  42. }

测试代码:

  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);
  3. // 输出:[1,9,20,11,18]
  4. echo json_encode($res);