How I can optimize the given below my python code?-CodePudding

I have an array and given an array of size N containing positive integers and I want to count number of smaller elements on right side of each array.

for example:-

    Input:
    N = 7
    arr[] = {12, 1, 2, 3, 0, 11, 4}
    Output: 6 1 1 1 0 1 0
    Explanation: There are 6 elements right
    after 12. There are 1 element right after
    1. And so on.
    

And my code for this problem is like as :- 
# python code here
    n=int(input())
    arr=list(map(int,input().split()))

    ans=0
    ANS=[]
    for i in range(n-1):
        for j in range(i 1,n):
            if arr[i]>arr[j]:
                ans =1
        ANS.append(ans)
        ans=0
    ANS.append(0)
    print(ANS)

but the above my code take O(n^2) time complexity and I want to reduce the this. If anyone have any idea to reduce above python code time complexity please help me. Thank you.

CodePudding user response：

This solution is O(n log(n)) as it is three iterations over the values and one sorting.

arr = [12, 1, 2, 3, 0, 11, 4]

# Gather original index and values
tups = []
for origin_index, el in enumerate(arr):
    tups.append([origin_index, el])

# sort on value
tups.sort(key=lambda t: t[1])

res = []
for sorted_index, values in enumerate(tups):
    # check the difference between the sorted and original index
    # If there is a positive value we have the n difference smaller 
    # values to the right of this index value. 
    if sorted_index - values[0] > 0:
        res.append([values[0], (sorted_index - values[0])])
    elif sorted_index - values[0] == 0:
        res.append([values[0], (sorted_index - values[0])   1])
    else:
        res.append([values[0], 0])

origin_sort_res = [0 for i in range(len(arr))]
for v in res:
    # Return the from the sorted array to the original indexing
    origin_sort_res[v[0]] = v[1]

print(origin_sort_res)

CodePudding user response：

try this(nlog2n)

def solution(nums):
    sortns = []
    res = []
    for n in reversed(nums):
        idx = bisect.bisect_left(sortns, n)
        res.append(idx)
        sortns.insert(idx,n)
    return res[::-1]

print(solution([12, 1, 2, 3, 0, 11, 4]))
# [6, 1, 1, 1, 0, 1, 0]