和五个最小数[重复]

Question

给定一个整数数组，什么算法将返回五个最小数字的和？我想通过一次传递来实现这一点，而不依赖于排序算法。

考虑到我们不能只对输入数组进行排序并得到五个最小的数字，我计划在开始时存储前五个数字，然后比较其余的输入并继续存储五个最小的数字。但是，如果没有排序算法，我如何提取第一个最小的五个呢？

Answer 1

选择最初的五个数字并不需要在查看数组的其余部分之前选择五个最小的数字：如果选择了，则无需查看数组的其余部分。

让我们通过为您的方法编写签名来简化此过程：

getSmallest(array<int> input, int nSmallest) -> array<int> # length of nSmallest

这种方法有什么作用？

• 将第一个最小的元素放入输出数组

生成的输出数组将保存所有最小的元素，并且不会对任何内容进行排序。让我们编写一些伪代码，首先检查输出数组：

# returns true if the candidate was swapped in, false otherwise.
# NOTE: outputArray and candidate can be modified by this function!
# If boolean is 'true' then 'candidate' will contain the swapped out element
swapElement(array<int> outputArray, int candidate) -> boolean
  foreach idx->smallNumber in outputArray
    if (candidate < smallNumber) {
      outputArray[idx] = candidate
      candidate = smallNumber
      return true
    }
  return false

既然我们已经处理了这个核心问题，我们如何使用解决方案？

getSmallest(array<int> input, int nSmallest) -> array<int>
  output[nSmallest] = copy(input, nSmallest) # copies the first nSmallest elements into output
  # Iterate through the remainder of the list
  for (idx = nSmallest, length(input), idx++) {
    checkingCandidate = true
    candidate = input[idx]
    while (checkingCandidate){ # This ensures that swapped candidates get checked too, no matter how many
      checkingCandidate = swapElement(output, candidate)
    } # This will quit once we are no longer swapping elements.
  }
  return output

现在您有了完整的解决方案—伪代码。正如您所看到的，核心问题是拥有输出数组，并在找到它时交换较小的元素（防止您需要先对数组排序）。一旦您将问题归结为“x元素是否比y数组中的任何元素都小”，剩下的就是迭代。哦，最后您只需将输出数组中的所有数字相加，这应该很简单。

Answer 2

遍历数组并将元素放入大小为5的最大堆中。因此，最后最大堆中存在的元素是最小的元素，它们的总和将导致所需的答案。

对于数组中的每个元素（比如x），检查它是否小于max堆中的max元素。如果它很小，则将堆中的max元素替换为x。否则只需转到下一个元素。

最后，堆中只有5个最小的元素。

Answer 3

您可以使用选择算法，其中k为5。您可以将列表从头返回为k并对所有数字求和。如果您对中位数进行中位数，则为O（n）。

该算法依赖于某些排序所依赖的相同的分区例程（想想快速排序）。但是，它不会对元素进行排序。