Imprima los elementos de array X más cercanos al K-ésimo elemento más pequeño de la array

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 =" ");
    
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *