Imprime n elementos más pequeños de una array dada en su orden original

Nos dan una array de m elementos, necesitamos encontrar los n elementos más pequeños de la array, pero deben estar en el mismo orden en que están en la array dada.

Ejemplos: 

Input : arr[] = {4, 2, 6, 1, 5}, 
        n = 3
Output : 4 2 1
Explanation : 
1, 2 and 4 are 3 smallest numbers and
4 2 1 is their order in given array.

Input : arr[] = {4, 12, 16, 21, 25},
        n = 3
Output : 4 12 16
Explanation : 
4, 12 and 16 are 3 smallest numbers and 
4 12 16 is their order in given array.

Haga una copia de la array original y luego ordene la array de copia. Después de ordenar la array de copia, guarde los n números más pequeños. Además, para cada elemento en la array original, verifique si está en el número n más pequeño o no, si está presente en la array n más pequeña, luego imprímalo, de lo contrario avance.  

Hacer copy_arr[]sort(copy_arr)Para todos los elementos en arr[] – Encuentra arr[i] en el elemento n-más pequeño de copy_arr Si lo encuentra, imprima el elemento

A continuación se muestra la implementación del enfoque anterior: 

// CPP for printing smallest n number in order
#include <bits/stdc++.h>
using namespace std;
 
// Function to print smallest n numbers
void printSmall(int arr[], int asize, int n)
{
    // Make copy of array
    vector<int> copy_arr(arr, arr + asize);
 
    // Sort copy array
    sort(copy_arr.begin(), copy_arr.begin() + asize);
 
    // For each arr[i] find whether
    // it is a part of n-smallest
    // with binary search
    for (int i = 0; i < asize; ++i)
        if (binary_search(copy_arr.begin(),
                copy_arr.begin() + n, arr[i]))
            cout << arr[i] << " ";
}
 
// Driver program
int main()
{
    int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
    int asize = sizeof(arr) / sizeof(arr[0]);   
    int n = 5;
    printSmall(arr, asize, n);
    return 0;
}

// Java for printing smallest n number in order
import java.util.*;
 
class GFG
{
 
 
// Function to print smallest n numbers
static void printSmall(int arr[], int asize, int n)
{
    // Make copy of array
    int []copy_arr = Arrays.copyOf(arr,asize);
 
    // Sort copy array
    Arrays.sort(copy_arr);
 
    // For each arr[i] find whether
    // it is a part of n-smallest
    // with binary search
    for (int i = 0; i < asize; ++i)
    {
        if (Arrays.binarySearch(copy_arr,0,n, arr[i])>-1)
            System.out.print(arr[i] + " ");
    }
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
    int asize = arr.length;
    int n = 5;
    printSmall(arr, asize, n);
}
}
 
// This code is contributed by Princi Singh

# Python3 for printing smallest n number in order
 
# Function for binary_search
def binary_search(arr, low, high, ele):
    while low < high:
        mid = (low + high) // 2
        if arr[mid] == ele:
            return mid
        elif arr[mid] > ele:
            high = mid
        else:
            low = mid + 1
    return -1
 
# Function to print smallest n numbers
def printSmall(arr, asize, n):
 
    # Make copy of array
    copy_arr = arr.copy()
 
    # Sort copy array
    copy_arr.sort()
 
    # For each arr[i] find whether
    # it is a part of n-smallest
    # with binary search
    for i in range(asize):
        if binary_search(copy_arr, low = 0,
                         high = n, ele = arr[i]) > -1:
            print(arr[i], end = " ")
 
# Driver Code
if __name__ == "__main__":
    arr = [1, 5, 8, 9, 6, 7, 3, 4, 2, 0]
    asize = len(arr)
    n = 5
    printSmall(arr, asize, n)
 
# This code is contributed by
# sanjeev2552

// C# for printing smallest n number in order
using System;    
 
class GFG
{
 
 
// Function to print smallest n numbers
static void printSmall(int []arr, int asize, int n)
{
    // Make copy of array
    int []copy_arr = new int[asize];
    Array.Copy(arr, copy_arr, asize);
 
    // Sort copy array
    Array.Sort(copy_arr);
 
    // For each arr[i] find whether
    // it is a part of n-smallest
    // with binary search
    for (int i = 0; i < asize; ++i)
    {
        if (Array.BinarySearch(copy_arr, 0, n, arr[i])>-1)
            Console.Write(arr[i] + " ");
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
    int asize = arr.Length;
    int n = 5;
    printSmall(arr, asize, n);
}
}
 
// This code has been contributed by 29AjayKumar

<script>
// Javascript for printing smallest n number in order
 
// Function to print smallest n numbers
function printSmall(arr, asize, n)
{
 
    // Make copy of array
    let copy_arr = [...arr];
 
    // Sort copy array
    copy_arr.sort((a, b) => a - b);
 
    // For each arr[i] find whether
    // it is a part of n-smallest
    // with binary search
    for (let i = 0; i < asize; ++i) {
        if (arr[i] < copy_arr[n])
            document.write(arr[i] + " ");
    }
}
 
// Driver program
let arr = [1, 5, 8, 9, 6, 7, 3, 4, 2, 0];
let asize = arr.length;
let n = 5;
printSmall(arr, asize, n);
 
// This code is contributed by gfgking.
</script>

Producción : 

1 3 4 2 0 

Complejidad de tiempo: O(n * log(n))

Espacio auxiliar: O(n)
Para hacer una copia de la array, necesitamos una complejidad de espacio de O(n) y luego, para ordenar, necesitamos una complejidad de orden O(n log n). Además, para cada elemento en arr[], estamos realizando una búsqueda en copy_arr[], lo que dará como resultado O(n) para la búsqueda lineal, pero podemos mejorarlo aplicando la búsqueda binaria y, por lo tanto, nuestra complejidad de tiempo general será O(n log n) .