Just trying to solve this problem:

Given an unsorted array of integers, sum its biggest n numbers.

I did a TypeScript implementation, but of course this is language agnostic:

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

Here in the playground.

My first question is if, when solving this kind of problems, the use of the methods provided by the language —as Array.sort()— are allowed, or if I should implement everything by myself, keeping the solution low level.

Also, I am not sure that this is the best way to solve it. I would say that this is O(n), but I am not taking into account the Arrayt.sort() method I'm using.

CodePudding user response：

Sorting is already O(n logn). It can be an easy solution when making use of the built-in sort functionality, but it is not going to be the most efficient solution to the problem.

If you are looking for a more efficient solution for this problem, you can just keep picking out (and removing) the biggest number k times, by iterating (or by using Quickselect). You can sum them together as you go, without having to store them in a new array and iterate again. This would actually be O(n) per number, so O(kn) in total.

This will be more efficient for small or constant k. Of course, if for instance you know that k = O(n), then better approaches exist.

As to whether it's ok to use built-in functions: Yes, definitely. Whenever they suit your purpose, it is better to use them than to reinvent the wheel every time. However, in an academic or challenge context, there might be rules in place disallowing use of libraries or built-in functions, for educational or competitive reasons.

CodePudding user response：

First of all, I will not delve into the question whether you are allowed to call library sort or not. This is up to you and your professor/boss/task.

Instead, I will delve into the question of whether you should do it. Imagine a case when you have 1 000 000 items in your array. The initial sort only has an O(n * log(n)) complexity, which is a high cost.

Instead, I would do it the following way:

1. Taking the first n item

Create an array, let's call it output (and the input will be called input here). Copy the first n (unsorted) elements from input into output.

2. Sort output

Yes, this is an algorithm of nlog(n) complexity, but your output is likely to be much smaller than your input.

3. Continue the loop

Continue looping your input from the (n 1)th element and for each element compare it with the smallest element in output (this is why we sorted output). If the smallest element of output is greater than the current element, then do nothing in this iteration. Otherwise find the greatest element of output that is still smaller than the current element, shift everything smaller to the left in output and put the current element into its right place.

Example logic in Javascript

function(item, output) {
    let highestIndex = -1;
    while ((output[highestIndex   1] < item) && (highestIndex   1 < output.length)) highestIndex  ;
    if (highestIndex >= 0) {
        for (let index = 0; index < highestIndex; index  ) output[index] = output[index   1];
    output[highestIndex] = item;
    }
}

4. Take into account edge cases

if n is 0, then the result is 0, no need for any loop
if n equals the length of input, then just sum input
if n is negative or greater than the length of input, throw an error

These edge cases are important, you can easily increase performance for them.