def foo(numbers): 
    result = [] 
    for i in range(len(numbers)): 
        sub = sorted(numbers[i:]) 
        result.append(sub[0]) 
    return result

Need to rewrite an asymptotically most efficient implementation of the function foo(numbers) mentioned above. The function must not modify the parameter numbers.

The implementation must be such that a list of numbers with 10^5 elements can be processed in less than a second.

The testing cases are:

1. foo(list(range(10**5)))
   print("ok")

2. print(foo([1,2,4,3]))

3. print(foo([8, 7]))

4. print(foo([5]))

5. print(foo([3, 3, 2, 1]))

Expected results from the testing cases:

1. ok
2. [1, 2, 3, 3]
3. [7, 7]
4. [5]
5. [1, 1, 1, 1]

My 1st attempt is using recursive but the code runner bans the sorted function and the code doesn't pass the 10^5 elements test:

def foo(numbers):
if len(numbers) <= 1:
    return [(sorted(numbers))[0]]
else:
    return [(sorted(numbers))[0]]   foo(numbers[1:])

My 2nd attempt is using insertion sort. It pass the 10^5 elements test but it doesn't get all the desired results

def foo(numbers):

    for i in range(len(numbers)):
        num = numbers[i]
        j=i
            
        while j >= 1 and numbers[j-1] > num:
            numbers[j] = numbers[j-1]
            j -= 1
            numbers[j] = num           
    return numbers

CodePudding user response：

Solve the problem from last index down to the first one, each time update your current minimum with the current number.

def foo(numbers): 
    result = [] 
    tmp = numbers[::-1]
    mn = tmp[0]
    for i in range(len(numbers)):
        mn = min(mn,tmp[i])
        result.append(mn)
    result = result[::-1]
    return result

CodePudding user response：

This seems to fulfil the brief:

import time

def foo(numbers): 
    mn = numbers[-1]
    return [mn := min(mn, t) for t in numbers[::-1]][::-1]

s = time.perf_counter()
foo(list(range(10**5)))
e = time.perf_counter()
print(f'Duration: {e-s:.4f}s')
print(foo([1,2,4,3]))
print(foo([8,7]))
print(foo([5]))
print(foo([3,3,2,1]))

Output:

Duration: 0.0190s
[1, 2, 3, 3]
[7, 7]
[5]
[1, 1, 1, 1]