Get the largest absolute difference in an array Python-CodePudding

I want to do a for loop that can basically do the absolute difference between every 2 elements of the array until it reaches all of them and then print the highest absolute difference.

arr = []

n = int(input("number of elements in array: "))

for i in range(0, n):
        arr.append(input('insert element: '))

I've done this already but I would like to know how slow this method is compared to making the absolute difference between the first and last element after sorting the array.

EXAMPLE

Input: {2, 7, 3, 4, 1, 9}

Output: 8 (|1 – 9|)

This is what I have tried:

arr = [] 
n = int(input("número de elementos do array : ")) 

for i in range(0, n): 
    arr.append(int(input('escreva os elementos: '))) 
    arr.sort() 
    print(arr[-1] - arr[0])

CodePudding user response：

As I understood about your query. Sorting the element and then comparing first & last one is much faster than finding highest difference via iterating through list. This is because when sorting happens internally, as it moves forward it needs to compare with less values because if value is higher than last sorted value it directly appends next to it but if value is less then it just moves one value back rather than starting over again. But comparing through all possible pairs in list takes much more time as it has to start from first value over again since we don't know which comparing will be highest. So sorting is much faster to find largest difference than iterating for every possible pair with for loop in list.

I hope I got your query right :)

UPDATED

so the main question is about finding a way to find largest diff in a list with for loop and which should be faster so here it is.

In my opinion below code will be even faster than sorting and finding largest diff. Because here in this code we only need to iterate in list once and we will have answer of largest diff. No need to iterate every possible pair of value.

I think this may help :)

list_a = []

n = int(input("number of elements in array: "))

for i in range(0, n):
    # store input after converting to integer.
    list_a.append(int(input('insert element: ')))
    
'''to store largest difference of two current numbers in every 
eteration'''
largest_diff_so_far = 0;
'''list to store that two numbers we are comparing'''
actual_diff_number = None;
'''start from first number in list. we don't need to go through 
every possible pair so just picking first number without for 
loop.'''
first = list_a[0]

'''here we iterate through all number only once till last number in list'''
for second in list_a :
    '''first find diff of current two value'''
    current_diff = second - first
    
    '''as we can see when current_diff is larger then previous largest diff we will update their value'''
    if largest_diff_so_far == 0 or current_diff > largest_diff_so_far:
        '''largest diff will be current_diff'''
        largest_diff_so_far = current_diff
        '''storing actual number whose diff is largest till now.'''
        actual_diff_number = [first, second]
    
    '''below is main part for saving time. if in current process we find diff which is in minus means our second value is even less than first, in that case we no longer need to carry forward that first value so we will update first value to our current second value and will also update largest diff that is stored previously. since our first value is less than previous first value then our diff will also increase from previous diff.'''
    if current_diff < 0:
        first = second
        '''update largest diff with new first value'''
        largest_diff_so_far = actual_diff_number[1] - first
        '''update actual diff number"s first value in that list'''
        actual_diff_number[0] = first

'''finally print answer since after finishing for loop largest_diff_so_far and actual_diff_number contains the answer that we are finding.'''
print(actual_diff_number, largest_diff_so_far)

CodePudding user response：

If you are fine with numpy, there's a way to do so.

Firstly, you need to find all the possible non-duplicate solutions from the given input using itertools.combinations

from itertools import combinations

alist = [2, 7, 3, 4, 1, 9]

all_comb = list(combinations(alist, 2))
[(2, 7), (2, 3), (2, 4), (2, 1), (2, 9), (7, 3), (7, 4), (7, 1), (7, 9), (3, 4), (3, 1), (3, 9), (4, 1), (4, 9), (1, 9)]

With this, you can use np.diff to find the differences for every tuple.

abs_diff = abs(np.diff(all_comb)).flatten()
array([5, 1, 2, 1, 7, 4, 3, 6, 2, 1, 2, 6, 3, 5, 8])

Finally, you can get the index of the maximum difference using np.argmax.

all_comb[abs_diff.argmax()]
Out[147]: (1, 9)

CodePudding user response：

arr = [] 
n = int(input("número de elementos do array : "))

my_min, my_max = None, None
for i in range(0, n): 
    arr.append(int(input('escreva os elementos: ')))
    if my_min is None or abs(arr[i]) < my_min:
        my_min = arr[i]
    if my_max is None or abs(arr[i]) > my_max:
        my_max = arr[i]
    print(f"{abs(my_max - my_min)} (|{my_max} - {my_min}|)")

You can achieve this just by "emembering" the number with highest and lowest abs value