Dados dos enteros K , X y una array arr[] que consta de N elementos distintos, la tarea es encontrar los elementos X más cercanos al K -ésimo elemento más pequeño de la array dada .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 10}, K = 3, X = 2
Salida: 2 3
Explicación: El elemento más pequeño presente en la array dada es 3 y X(= 2) la array más cercana los elementos a 3 son {2, 3} o {3, 4}.
Por lo tanto, la salida requerida es 2 3.Entrada: arr[] = {1, 9, 8, 2, 7, 3, 6, 4, 5, 10, 13, 12, 16, 14, 11, 15}, K = 3, X = 5
Salida: 1 2 3 4 5
Enfoque ingenuo: el enfoque más simple para resolver este problema es ordenar la array e imprimir los X elementos más cercanos al K -ésimo elemento más pequeño de la array dada utilizando la técnica de dos punteros .
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es calcular de manera eficiente el valor del K -ésimo elemento más pequeño de la array dada utilizando el Algoritmo de selección de la mediana . Siga los pasos a continuación para resolver el problema:
- Calcule el Kth más pequeño, digamos KthElem de la array dada usando el algoritmo de selección de la mediana .
- Inicialice una array, diga diff[] para almacenar la diferencia absoluta de arr[i] y KthElem .
- Cree un mapa , digamos mapas para mapear cada elemento de la array a la diferencia absoluta del elemento actual y KthElem .
- Recorre la array dada y agrega arr[i] a maps[abs(KthElem – arr[i])] .
- Calcule el X elemento más pequeño, digamos XthElem de la array diff[] usando el algoritmo de selección de la mediana para imprimir exactamente los X elementos más cercanos.
- Finalmente, recorra la array diff[] y verifique si XthElem es menor o igual que diff[i] o no. Si se encuentra que es cierto, imprima el elemento de la array con la ayuda de mapas .
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python3 program to implement # the above approach import collections # Function to swap # two elements of array def swap(arr, a, b): temp = arr[a] arr[a] = arr[b] arr[b] = temp # Function to partition # the array around x def partition(arr, l, r, x): # Traverse array # from index l to r for i in range(l, r): # partition array # around x if arr[i] == x: swap(arr, r, i) break x = arr[r] i = l # Traverse array # from index l to r for j in range(l, r): if (arr[j] <= x): swap(arr, i, j) i += 1 swap(arr, i, r) return i # Function to find # median of arr[] # from index l to l + n def findMedian(arr, l, n): lis = [] for i in range(l, l + n): lis.append(arr[i]) # Sort the array lis.sort() # Return middle element return lis[n // 2] # Function to get # the kth smallest element def kthSmallest(arr, l, r, k): # If k is smaller than # number of elements # in array if (k > 0 and k <= r - l + 1): # Stores count of # elements in arr[l..r] n = r - l + 1 # Divide arr[] in groups # of size 5, calculate # median of every group # and store it in # median[] array. median = [] i = 0 while (i < n // 5): median.append( findMedian(arr, l + i * 5, 5)) i += 1 # For last group with # less than 5 elements if (i * 5 < n): median.append( findMedian(arr, l + i * 5, n % 5)) i += 1 # If median[] has # only one element if i == 1: medOfMed = median[i - 1] # Find median of all medians # using recursive call. else: medOfMed = kthSmallest( median, 0, i - 1, i // 2) # Stores position of pivot # element in sorted array pos = partition(arr, l, r, medOfMed) # If position is same as k if (pos - l == k - 1): return arr[pos] # If position is more, if (pos - l > k - 1): # recur for left subarray return kthSmallest(arr, l, pos - 1, k) # Else recur for right subarray return kthSmallest(arr, pos + 1, r, k - pos + l - 1) # If k is more than # number of elements # in the array return 999999999999 # Function to print def closestElements(arr, k, x): # Stores size of arr n = len(arr) # Stores kth smallest # of the given array KthElem = kthSmallest( arr, 0, n - 1, k) # Store the value of # abs(KthElem - arr[i]) diff = [] # Create a map to map # array element to # abs(KthElem - arr[i]) maps = collections.defaultdict( list) for elem in arr: # Stres the value of # abs(elem - KthElem) temp = abs(elem - KthElem) # map array elements maps[temp].append(elem) # append temp diff.append(temp) XthElem = kthSmallest(diff, 0, n - 1, x) # Store X closest elements res = set() # Traverse diff[] array for dx in diff: # If absolute difference is # less than or equal to XthElem if dx <= XthElem: # Append closest elements for elem in maps[dx]: if len(res) < x: res.add(elem) return res # Driver Code if __name__ == '__main__': arr = [1, 2, 3, 4, 10, 15] k = 3 x = 2 # Store X closest elements res = closestElements(arr, k, x) # Print X closest elements for i in res: print(i, end =" ");
2 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por BIRANCHINARAYANPADHI y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA