algorithm - 对未排序数组中最大的 n 个数求和

Question

只是想解决这个问题:

给定一个未排序的整数数组，对它最大的 n 个数求和。

我做了一个 TypeScript 实现，但这当然与语言无关:

const list_sum_largest_n_numbers = (list: Array<number> = [], n: number) => {
  let sum: number = 0;
  const sorted_list = list.sort((a, b) => a - b);

  for (let i = 0; i < n; i++) {
    let value_to_sum = sorted_list?.pop() || 0;
    sum += value_to_sum;
  }

  return sum;
};

let list = [17, 310, 32_432, 3, 2, 317, 34, 108_379];
let n = 3;

let result = list_sum_largest_n_numbers(list, n);
alert(result); // 141_128

在 playground 中.

我的第一个问题是，在解决这类问题时，是否允许使用语言提供的方法——如 Array.sort()——，或者我是否应该通过我自己，将解决方案保持在低水平。

此外，我不确定这是解决问题的最佳方法。我会说这是 O(n)，但我没有考虑我正在使用的 Array.sort() 方法。

Answer 1

排序已经是 O(n logn)。当使用内置排序功能时，它可能是一个简单的解决方案，但它不会是解决问题的最有效解决方案。

简单的解决方案 O(kn)

如果您正在为这个问题寻找更有效但更简单的解决方案，您可以通过迭代不断挑选(并删除或标记为已访问)最大数 k 次。您可以随时将它们加在一起，而不必将它们存储在一个新数组中并再次迭代。这实际上是每个数字 O(n)，因此总共 O(kn)。

这对于小的或恒定的 k 会更有效。当然，例如，如果您知道 k = O(n)，则存在更好的方法。

高效的解决方案 O(n)

对于稍微简单一点的解决方案，您可以使用 Quickselect找到第 k 个最大的数 x 然后在一次迭代中将所有大于 x 的数加在一起，然后加上 x 和可能剩余的重复值(或者如 rici 指出的那样，只在 x 的右侧迭代，因为 quickselect 对数组进行分区对我们有利)。这将为您提供 O(n) 加法运算的总时间复杂度。这是渐近性能和代码复杂性之间的权衡:)

关于使用内置排序

至于是否可以使用内置函数:可以，可以。每当它们适合您的目的时，最好使用它们而不是每次都重新发明轮子。但是，在学术或挑战环境中，出于教育或竞争原因，可能存在禁止使用库或内置函数的规则。