We can assign all the numbers in a list a unique value that upon repetition it retains that value retained to it. This is a very common problem that is faced in web development when playing with id’s. Let’s discuss certain ways in which this problem can be solved.
Method #1: Using enumerate() + list comprehension
List comprehension can be used to perform this particular task along with the enumerate function which selects the unique numbers with the help of set and former helping in the iteration in the list.
Python3
# Python3 code to demonstrate# assign unique value to list elements# using list comprehension + enumerate# initializing listtest_list = [1, 4, 6, 1, 4, 5, 6]# printing the original listprint("The original list is : " + str(test_list))# using list comprehension + enumerate# assign unique value to list elementstemp = {i: j for j, i in enumerate(set(test_list))}res = [temp[i] for i in test_list]# printing resultprint("The unique value list is : " + str(res)) |
The original list is : [1, 4, 6, 1, 4, 5, 6] The unique value list is : [0, 1, 3, 0, 1, 2, 3]
Time Complexity: O(n*n), where n is the length of the input list. This is because we’re using enumerate() + list comprehension which has a time complexity of O(n*n) in the worst case.
Auxiliary Space: O(n), as we’re using additional space res other than the input list itself with the same size of input list.
Method #2 : Using setdefault() + map() + count()
The combination of all the three function can also be used to perform this particular task. Map binds all the like elements, setdefault assigns them unique number and count function helps map to find number of total occurrences.
Python3
# Python3 code to demonstrate# assign unique value to list elements# using setdefault() + map() + count()from itertools import count# initializing listtest_list = [1, 4, 6, 1, 4, 5, 6]# printing the original listprint("The original list is : " + str(test_list))# using setdefault() + map() + count()# assign unique value to list elementsres = list(map({}.setdefault, test_list, count()))# printing resultprint("The unique value list is : " + str(res)) |
The original list is : [1, 4, 6, 1, 4, 5, 6] The unique value list is : [0, 1, 2, 0, 1, 5, 2]
Time Complexity: O(n), where n is length of test_list.
Auxiliary Space: O(n), where n is length of res list.
Method #3: Using in , not in operators and index() method
Python3
# Python3 code to demonstrate# assign unique value to list elements# initializing listtest_list = [1, 4, 6, 1, 4, 5, 6]# printing the original listprint ("The original list is : " + str(test_list))# assign unique value to list elementsx=[]for i in test_list: if i not in x: x.append(i)res=[]for i in test_list: res.append(x.index(i)) # printing resultprint ("The unique value list is : " + str(res)) |
The original list is : [1, 4, 6, 1, 4, 5, 6] The unique value list is : [0, 1, 2, 0, 1, 3, 2]
Time Complexity: O(n), where n is the length of test_list.
Auxiliary Space: O(n), where n is length of res list.
Method #4: Using reduce():
- Import the reduce function from the functools module.
- Define a list test_list containing the input list of integers.
- Define a lambda function that takes two arguments: a list l and an integer x.
- The lambda function checks if the integer x is not already in the list l. If it is not, it adds the integer to the list, otherwise it returns the original list
- Call the reduce function with the lambda function, the input list test_list, and an initial value of an empty list [].
- The reduce function applies the lambda function cumulatively to the elements of the input list, and returns
- the final value of the list containing only the unique elements of test_list.
- Assign the resulting list to the variable unique_list.
- Define an empty list res to store the results.
- For each element i in the input list test_list, find the index of i in the unique_list using the index method
- Append the resulting index to the list res.
- Print the resulting list res.
Python3
from functools import reducetest_list = [1, 4, 6, 1, 4, 5, 6]# printing the original listprint ("The original list is : " + str(test_list)) unique_list = reduce(lambda l, x: l + [x] if x not in l else l, test_list, [])res = [unique_list.index(i) for i in test_list]# printing resultprint ("The unique value list is : " + str(res))#This code is contrinuted by Pushpa. |
The original list is : [1, 4, 6, 1, 4, 5, 6] The unique value list is : [0, 1, 2, 0, 1, 3, 2]
The time complexity : O(n^2), because the in operator inside the lambda function requires a linear search through the list for each element of the input list, resulting in a nested loop.
The space complexity :O(n^2), because the size of the unique_list can be up to n elements long, and the res list is also n elements long.
Method 5: Using sorted() and bisect_left()
In this approach, we first create a sorted copy of the original list. Then, we iterate over the sorted list and assign unique values to each element based on its position using the bisect_left() method from the bisect module.
step-by-step approach:
Create a sorted copy of the original list using the sorted() function.
Initialize an empty result list.
Iterate over the elements in the sorted list, and for each element, find its index using the bisect_left() method.
Append the index to the result list.
Return the result list.
Python3
# Python3 code to demonstrate# assign unique value to list elementsimport bisect# initializing listtest_list = [1, 4, 6, 1, 4, 5, 6]# printing the original listprint ("The original list is : " + str(test_list))# assign unique value to list elements using sorted() and bisect_left()sorted_list = sorted(test_list)res = []for i in test_list: idx = bisect.bisect_left(sorted_list, i) res.append(idx)# printing resultprint ("The unique value list is : " + str(res)) |
The original list is : [1, 4, 6, 1, 4, 5, 6] The unique value list is : [0, 2, 5, 0, 2, 4, 5]
Time complexity: O(nlogn), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list. We need to store a sorted copy of the input list.
Method 6: Using numpy:
Algorithm:
- Initialize an empty list to store unique values.
- Loop through each element of the given list.
- If the element is not present in the unique values list, add it to the list.
- Loop through each element of the given list again.
- For each element, find its index in the unique values list.
- Append the index to the result list.
- Return the result list.
Python3
import numpy as nptest_list = [1, 4, 6, 1, 4, 5, 6]# printing the original listprint("The original list is:", test_list)# convert list to numpy arrayarr = np.array(test_list)# get unique values and their indicesunique_arr, unique_indices = np.unique(arr, return_inverse=True)# get indices of unique values for each element in original listres = unique_indices.tolist()# printing resultprint("The unique value list is:", res)#This code is contributed by Vinay Pinjala. |
Output: The original list is: [1, 4, 6, 1, 4, 5, 6] The unique value list is: [0, 1, 3, 0, 1, 2, 3]
Time complexity: O(n^2), where n is the length of the given list. This is because we are using two nested loops to iterate over the list. In the worst case, when all elements are unique, the inner loop will run n times for each element in the outer loop, resulting in a quadratic time complexity.
Space complexity: O(n), where n is the length of the given list. This is because we are using an extra list to store the unique values, which can have a maximum length of n if all elements in the given list are unique. The result list also has a length of n.
