Given a Matrix, perform row sorting by number of multiple of K present in row.
Input : test_list = [[3, 4, 8, 1], [12, 32, 4, 16], [1, 2, 3, 4], [9, 7, 5]], K = 4
Output : [[9, 7, 5], [1, 2, 3, 4], [3, 4, 8, 1], [12, 32, 4, 16]]
Explanation : 0 < 1 < 2 < 4, multiple of 4 occurrence order.Input : test_list = [[3, 4, 8, 1], [12, 32, 4, 16], [1, 2, 3, 4], [9, 7, 5]], K = 2
Output : [[9, 7, 5], [1, 2, 3, 4], [3, 4, 8, 1], [12, 32, 4, 16]]
Explanation : 0 < 2 = 2 < 4, multiple of 2 occurrence order.
Method #1 : Using sort() + % operator + len()
In this, we test for multiple using % operator and then compute count by getting length of filtered elements, provided to key to sort() which performs inplace sorting of rows.
Python3
# Python3 code to demonstrate working of# Sort row by K multiples# Using sort() + % operator + len()# checking for multiples countdef k_mul(row): return len([ele for ele in row if ele % K == 0])# initializing listtest_list = [[3, 4, 8, 1], [12, 32, 4, 16], [1, 2, 3, 4], [9, 7, 5]]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 4# performing sorttest_list.sort(key=k_mul)# printing resultprint("Sorted result : " + str(test_list)) |
Output:
The original list is : [[3, 4, 8, 1], [12, 32, 4, 16], [1, 2, 3, 4], [9, 7, 5]]
Sorted result : [[9, 7, 5], [1, 2, 3, 4], [3, 4, 8, 1], [12, 32, 4, 16]]
Time Complexity: O(nlogn*mlogm)
Auxiliary Space: O(1)
Method #2 : Using sorted() + lambda + len()
In this, sorting is done using sorted(), len() is used to get length of all the multiples of K as in above method. The lambda function provides single statement alternative to perform logical injection.
Python3
# Python3 code to demonstrate working of# Sort row by K multiples# Using sorted() + lambda + len()# initializing listtest_list = [[3, 4, 8, 1], [12, 32, 4, 16], [1, 2, 3, 4], [9, 7, 5]]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 4# performing sort using sorted()# lambda avoiding external function callres = sorted(test_list, key=lambda row: len( [ele for ele in row if ele % K == 0]))# printing resultprint("Sorted result : " + str(res)) |
Output:
The original list is : [[3, 4, 8, 1], [12, 32, 4, 16], [1, 2, 3, 4], [9, 7, 5]]
Sorted result : [[9, 7, 5], [1, 2, 3, 4], [3, 4, 8, 1], [12, 32, 4, 16]]
Time Complexity: O(n*logn), where n is the length of the input list. This is because we’re using the built-in sorted() function which has a time complexity of O(nlogn) in the worst case.
Auxiliary Space: O(n), as we’re using additional space other than the input list itself.
