Given a List of elements, perform sort on basis of its distance from K.
Input : test_list = [6, 7, 4, 11, 17, 8, 3], K = 10
Output : [11, 8, 7, 6, 4, 17, 3]
Explanation : 11-10 = 1; < 10 – 8 = 2 .. Ordered by increasing difference.Input : test_list = [6, 7, 4, 11], K = 10
Output : [11, 7, 6, 4]
Explanation : 11-10 = 1; < 10 – 7 = 3 .. Ordered by increasing difference.
Method #1 : Using sort() + abs()
In this, we perform sorting using sort() and abs() is used to get the difference, used for logic formation to perform sort operation upon.
Python3
# Python3 code to demonstrate working of # Nearest K Sort # Using sort() + abs() # getting absolute difference def get_diff(ele): # returning absolute difference return abs(ele - K) # initializing list test_list = [6, 7, 4, 11, 17, 8, 3] # printing original list print("The original list is : " + str(test_list)) # initializing K K = 10 # performing inplace sort using sort() test_list.sort(key=get_diff) # printing result print("Sorted List : " + str(test_list)) |
The original list is : [6, 7, 4, 11, 17, 8, 3] Sorted List : [11, 8, 7, 6, 4, 17, 3]
Time Complexity: O(n*nlogn) where n is the number of elements in the list “test_list”. sort() + abs() performs n*nlogn number of operations.
Auxiliary Space: O(n), extra space is required where n is the number of elements in the list
Method #2 : Using sorted() + lambda + abs()
Similar to above method, here, sorted() is used to perform sort operation and rather than calling external function, lambda is used to provide sorting logic.
Python3
# Python3 code to demonstrate working of # Nearest K Sort # Using sorted() + abs() + lambda # initializing list test_list = [6, 7, 4, 11, 17, 8, 3] # printing original list print("The original list is : " + str(test_list)) # initializing K K = 10 # sorted() used to perform sorting, lambda function to get logic res = sorted(test_list, key=lambda ele: abs(ele - K)) # printing result print("Sorted List : " + str(res)) |
The original list is : [6, 7, 4, 11, 17, 8, 3] Sorted List : [11, 8, 7, 6, 4, 17, 3]
Method #3: Using heapq.nsmallest()
Import the heapq module.
Initialize an empty list to store the absolute difference between each element of the given list and the given value of K.
Use a for loop to iterate through the given list.
Calculate the absolute difference between the current element and the given value of K using the abs() function, and append it to the list initialized in step 2.
Use the heapq.nsmallest() function to find the K nearest elements to the given value of K. This function returns a list of the K smallest elements from the given list in ascending order.
Print the resulting list.
Python3
import heapq test_list = [6, 7, 4, 11, 17, 8, 3] K = 10 # Initialize an empty list to store the absolute difference abs_diff = [] # Calculate the absolute difference between each element and K for num in test_list: abs_diff.append(abs(num - K)) # Use heapq.nsmallest() to find the K nearest elements res = heapq.nsmallest(K, test_list, key=lambda x: abs(x - K)) print("Nearest K elements to", K, ":", res) |
Nearest K elements to 10 : [11, 8, 7, 6, 4, 17, 3]
Time complexity: O(n log K) where n is the length of the given list and K is the number of elements to be returned.
Auxiliary space: O(n) for storing the absolute difference between each element and the given value of K.
