Hướng dẫn rank transformation python

Python Beginner Algorithms Tutorial

April 10, 2020
Key Terms: functions, loops, lists, dictionaries, zip function

This problem is on Leetcode.

Problem statement:

Given an array of integers arr, replace each element with its rank. The rank represents how large the element is in the array. The rank has the following rules:

Rank is an integer starting from 1.
The larger the element, the larger the rank.
If two elements are equal, their rank must be the same.

Define Test Cases¶

In [16]:

# assert array_rank_transform([40, 10, 20, 30]) == [4, 1, 2, 3]

40 is the 4th smallest number in the array (smaller than no other number)
10 is the 1st smallest number in the array (smaller than 20, 30 and 40
20 is the 2nd smallest number in the array (smaller than 30 and 40)
30 is the 3rd smallest number in the array (smaller than 40)

In [17]:

# assert array_rank_transform([100, 100, 100]) == [1, 1, 1]

Remember elements of the same value can share the same rank value.

100 is the 1st smallest number in the array (tied with 100 and 100)
100 is the 1st smallest number in the array (tied with 100 and 100)
100 is the 1st smallest number in the array (tied with 100 and 100)

Explanation of Solution #1¶

Pseudocode for Solution #1¶

In [24]:

# create a function that takes an array as an input # use sorted function on input list to sort it from smallest to largest # assign variable rank to be integer rank value of 1 # assign variable sorted_rank_list to store list of final ranks and just one item of 1 # iterate over element in sorted list... # iterate i from 1 to the length of the sorted_list # want to compare value in iteration to previous value... # if sorted_list[i] == sorted_list[i-1] # the value in sorted list is same as previous value... # we want rank value to stay the same for equal values... # don't increase rank # else: # increment rank by 1 # append rank value to sorted_rank_list # assign rank_list to be an empty list # create rank_list values through use of sorted_list, input list and sorted_rank_list... # iterate over each item in original input list # for every index, element in enumerate(sorted_list): # if element is equal to item # want to find equivalent ranking for that number in sorted_list # append sorted_rank_list[index] to rank_list # break out of for loop to move to next number in original array # return rank_list

Code for Solution #1¶

In [19]:

def array_rank_transform(arr): sorted_list = sorted(arr) rank = 1 # seed initial rank as 1 because that's first item in input list sorted_rank_list = [1] for i in range(1, len(sorted_list)): if sorted_list[i] != sorted_list[i-1]: rank += 1 sorted_rank_list.append(rank) rank_list = [] for item in arr: for index, element in enumerate(sorted_list): if element == item: rank_list.append(sorted_rank_list[index]) # we want to break out of inner for loop break return rank_list

Verify Solution #1 with Test Cases¶

In [20]:

assert array_rank_transform([40, 10, 20, 30]) == [4, 1, 2, 3]

In [21]:

assert array_rank_transform([100, 100, 100]) == [1, 1, 1]

In [22]:

assert array_rank_transform([1, 3, 3, 5]) == [1, 2, 2, 3]

Complexity of Solution #1¶

Let n be the count of values in the input list.

Space complexity:

sorted_list will hold n values and therefore is O(n)
sorted_rank_list will hold n values and is O(n)
rank_list will hold n values and is O(n)

Total space complexity is O(3n). The 3 is insignificant so I'll round to O(n).

Time complexity:

Sort the input list is an O(nlogn) operation
Iteration over every value in sorted_list is O(n)
Iteration over each value in arr - the input list - is O(n)
Iteration over each index and value in sorted_list up to finding an equivalent value in the input list should be on average O(n/2); the division by 2 is insignificant so this will be O(n).

Total time eomplexity is also O(nlogn) + O(n) + O(n) + O(n) which equals O(3nlogn). The 3 is insignificant so I'll round to O(nlogn).

Explanation of Solution #2¶

Pseudocode for Solution #2¶

In [ ]:

# create a function that takes an array as an input # use sorted function on input list to sort it from smallest to largest # assign variable rank to be integer rank value of 1 # assign variable sorted_rank_list to store list of final ranks and just one item of 1 # iterate over element in sorted list... # iterate i from 1 to the length of the sorted_list # want to compare value in iteration to previous value... # if sorted_list[i] is not equal to sorted_list[i-1] # increment rank by 1 # append rank value to sorted_rank_list # rank_list and sorted_list are the same size... # create dictionary with each item as a key and its rank as the value... # dictionary called item_rank_dict # assign rank_list to be an empty list # iterate over each item in original input list # lookup rank of item in item_rank_dict and append value to rank_list # return rank_list

Code for Solution #2¶

In [ ]:

def array_rank_transform(arr): sorted_list = sorted(arr) rank = 1 sorted_rank_list = [1] for i in range(1, len(sorted_list)): if sorted_list[i] != sorted_list[i-1]: rank += 1 sorted_rank_list.append(rank) rank_list = [] # zip function returns iterator of tuple pairs of matching values in two inputss # dict function casts 1nd value in tuple as key and 2nd value in tuple as value item_rank_dict = dict(zip(sorted_list, sorted_rank_list)) for item in arr: item_rank = item_rank_dict[item] rank_list.append(item_rank) return rank_list

Complexity for Solution #2¶

Let n be the count of values in the input list.

Space complexity:

sorted_list will hold n values and therefore is O(n)
sorted_rank_list will hold n values and is O(n)
rank_list will hold n values and is O(n)
item_rank_dict will hold n values and is O(n)

Total space complexity is O(4n). The 4 is insignificant so I'll round to O(n).

Time complexity:

Sort the input list is an O(nlogn) operation
Iteration over every value in sorted_list is O(n)
Creation of item_rank_dict is an O(n) operation
Iteration over each value in arr - the input list - is O(n)

Total time complexity is O(3nlogn). The 3 is insignificant so I'll round to O(nlogn).

Verify Test Cases for Solution #2¶

In [27]: