"""
This implementation finds the three largest
numbers in an array in an efficient manner.
The idea is to maintain a subarray holding
the three largest values encountered so
far. When the algorithm concludes that
subarray would end up holding the desired
output value (i.e., 3 largest values of
main array).
Let n be the size of the array
Time complexity: O(n)
Space complexity: O(1)
"""
def find_three_largest_values(arr):
# Container for 3 largest values
result = [None]*3
# Make sure result holds always
# 3 largest values encountered so far
for val in arr:
update_result(result, val)
return result
def update_result(result, val):
# Insert val into appropriate position
# Only vals of interest are those bigger
# than values already in result array.
if result[2] is None or val > result[2]:
update_and_shift(result, val, 2)
elif result[1] is None or val > result[1]:
update_and_shift(result, val, 1)
elif result[0] is None or val > result[0]:
update_and_shift(result, val, 0)
def update_and_shift(result, val, idx):
for i in range(idx+1):
if i == idx:
result[i] = val
else:
result[i] = result[i+1]
arr = [1, 2, 3, 7, 8, 9]
print(find_three_largest_values(arr)) # [7, 8, 9]
array = [1, 2, 3, 4, 5, 6, 7, 8, 9, ]
result = []
num = int(input('Enter N: '))
for x in range(0, num):
largeNum = 0
for y in range(len(array)):
if array[y] > largeNum:
largeNum = array[y]
array.remove(largeNum)
result.append(largeNum)
print(result)