Encuentre el K-ésimo elemento mínimo de una array concatenada M veces

Posted on by Rudeus Greyrat

Dada una array arr[] y dos enteros K y M . El problema es encontrar el elemento Mínimo K-th después de concatenar la array a sí mismo M veces .
Ejemplos: 

Input  : arr[] = {3, 1, 2}, K = 4, M = 3 
Output : 4'th Minimum element is : 2
Explanation: Concatenate array 3 times (ie., M = 3)
              arr[] = [3, 1, 2, 3, 1, 2, 3, 1, 2]
              arr[] = [1, 1, 1, 2, 2, 2, 3, 3, 3]
              Now 4'th Minimum element is 2

Input  : arr[] = {1, 13, 9, 17, 1, 12}, K = 19, M = 7 
Output : 19'th Minimum element is : 9

Enfoque sencillo: 

  1. Agregue la array dada a un vector o cualquier otra array, digamos V por M veces.
  2. Ordene el vector o array V en orden ascendente.
  3. Devuelva el valor en el índice ( K-1 ) del vector V , es decir, devuelva V[ K – 1 ].

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

C++

// C++ programme to find the K'th minimum
// element from an array concatenated M times
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the K-th minimum element
// from an array concatenated M times
int KthMinValAfterMconcatenate(int A[], int N,
                                 int M, int K)
{
    vector<int> V;
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            V.push_back(A[j]);
        }
    }
 
    // sort the elements in ascending order
    sort(V.begin(), V.end());
 
    // return K'th Min element
    // present at K-1 index
    return (V[K - 1]);
}
 
// Driver Code
int main()
{
    int A[] = { 3, 1, 2 };
 
    int M = 3, K = 4;
    int N = sizeof(A) / sizeof(A[0]);
 
    cout << KthMinValAfterMconcatenate(A, N, M, K);
 
    return 0;
}

Java

import java.util.ArrayList;
import java.util.Collections;
 
// Java programme to find the K'th minimum
// element from an array concatenated M times
class GFG
{
 
    // Function to find the K-th minimum element
    // from an array concatenated M times
    static int KthMinValAfterMconcatenate(int[] A, int N,
            int M, int K)
    {
        ArrayList V = new ArrayList();
 
        for (int i = 0; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                V.add(A[j]);
            }
        }
 
        // sort the elements in ascending order
        Collections.sort(V);
 
        // return K'th Min element
        // present at K-1 index
        return ((int) V.get(K - 1));
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] A = {3, 1, 2};
        int M = 3, K = 4;
        int N = A.length;
        System.out.println(KthMinValAfterMconcatenate(A, N, M, K));
    }
}
 
/* This code contributed by PrinciRaj1992 */

Python3

# Python3 program to find the K'th minimum 
# element from an array concatenated M times
   
# Function to find the K-th minimum element 
# from an array concatenated M times
def KthMinValAfterMconcatenate(A, N, M, K):
  
    V = []
   
    for i in range(0, M): 
        for j in range(0, N): 
            V.append(A[j])
   
    # sort the elements in ascending order
    V.sort()
   
    # return K'th Min element
    # present at K-1 index
    return V[K - 1]
   
# Driver Code
if __name__ == "__main__":
  
    A = [3, 1, 2] 
   
    M, K = 3, 4
    N = len(A)
   
    print(KthMinValAfterMconcatenate(A, N, M, K))
   
# This code is contributed by Rituraj Jain

C#

// C# programme to find the K'th minimum
// element from an array concatenated M times
using System;
using System.Collections;
 
class GFG
{
     
// Function to find the K-th minimum element
// from an array concatenated M times
static int KthMinValAfterMconcatenate(int []A, int N,
                                int M, int K)
{
    ArrayList V=new ArrayList();
 
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            V.Add(A[j]);
        }
    }
 
    // sort the elements in ascending order
    V.Sort();
 
    // return K'th Min element
    // present at K-1 index
    return ((int)V[K - 1]);
}
 
// Driver Code
static void Main()
{
    int []A = { 3, 1, 2 };
 
    int M = 3, K = 4;
    int N = A.Length;
 
    Console.WriteLine(KthMinValAfterMconcatenate(A, N, M, K));
}
}
 
// This code is contributed by mits

PHP

<?php
// PHP programme to find the K'th minimum
// element from an array concatenated M times
 
// Function to find the K-th minimum element
// from an array concatenated M times
function KthMinValAfterMconcatenate($A, $N,
                                    $M, $K)
{
    $V = array();
 
    for ($i = 0; $i < $M; $i++)
    {
        for ($j = 0; $j < $N; $j++)
        {
            array_push($V, $A[$j]);
        }
    }
 
    // sort the elements in ascending order
    sort($V);
 
    // return K'th Min element
    // present at K-1 index
    return ($V[$K - 1]);
}
 
// Driver Code
$A = array( 3, 1, 2 );
 
$M = 3;
$K = 4;
$N = count($A);
 
echo KthMinValAfterMconcatenate($A, $N, $M, $K);
 
// This code is contributed by mits
?>

Javascript

<script>
 
 
// Javascript programme to find the K'th minimum
// element from an array concatenated M times
 
// Function to find the K-th minimum element
// from an array concatenated M times
function KthMinValAfterMconcatenate(A, N, M, K)
{
    var V = [];
 
    for (var i = 0; i < M; i++) {
        for (var j = 0; j < N; j++) {
            V.push(A[j]);
        }
    }
 
    // sort the elements in ascending order
    V.sort();
 
    // return K'th Min element
    // present at K-1 index
    return (V[K - 1]);
}
 
// Driver Code
var A = [3, 1, 2];
var M = 3, K = 4;
var N = A.length;
document.write( KthMinValAfterMconcatenate(A, N, M, K));
 
</script>
Producción

2

Complejidad de tiempo: O((M * N) * log(M * N))
Espacio auxiliar: O(M * N)

Enfoque eficiente: el enfoque anterior funcionará bien si el valor de M es pequeño, pero para 
un valor grande de M dará un error de memoria o un error de tiempo de espera.
La idea es observar que después de ordenar la array dada cuando la concatenamos M veces y la volvemos a ordenar, cada elemento ahora aparecerá M veces en la nueva array concatenada. Asi que, 
 

  1. Ordenar la array dada en orden ascendente.
  2. Devuelve el valor presente en el índice ((K-1) / M) de la array dada, es decir, devuelve arr[((K-1) / M)].

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

C++

// C++ programme to find the K'th minimum element
// from an array concatenated M times
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the K-th minimum element
// from an array concatenated M times
int KthMinValAfterMconcatenate(int A[], int N,
                                  int M, int K)
{
    // Sort the elements in
    // ascending order
    sort(A, A + N);
 
    // Return the K'th Min element
    // present at ( (K-1) / M ) index
    return (A[((K - 1) / M)]);
}
 
// Driver Code
int main()
{
    int A[] = { 3, 1, 2 };
 
    int M = 3, K = 4;
    int N = sizeof(A) / sizeof(A[0]);
 
    cout << KthMinValAfterMconcatenate(A, N, M, K);
 
    return 0;
}

Java

// Java programme to find the K'th minimum element
// from an array concatenated M times
import java.util.*;
 
class GFG1
{
 
    // Function to find the K-th minimum element
    // from an array concatenated M times
    static int KthMinValAfterMconcatenate(int[] A, int N,
                                            int M, int K)
    {
        // Sort the elements in
        // ascending order
        Arrays.sort(A);
 
        // Return the K'th Min element
        // present at ( (K-1) / M ) index
        return (A[((K - 1) / M)]);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int[] A = {3, 1, 2};
 
        int M = 3, K = 4;
        int N = A.length;
 
        System.out.println(KthMinValAfterMconcatenate(A, N, M, K));
    }
}
 
// This code contributed by Rajput-Ji

Python3

# Python3 program to find the K'th minimum
# element from an array concatenated M times
 
# Function to find the K-th minimum element
# from an array concatenated M times
def KthMinValAfterMconcatenate(A, N, M, K):
 
    V = []
 
    for i in range(0, M):
        for j in range(0, N):
            V.append(A[j])
 
    # sort the elements in ascending order
    V.sort()
 
    # return K'th Min element
    # present at K-1 index
    return V[K - 1]
 
# Driver Code
if __name__ == "__main__":
 
    A = [3, 1, 2]
 
    M, K = 3, 4
    N = len(A)
 
    print(KthMinValAfterMconcatenate(A, N, M, K))
 
# This code is contributed by Rituraj Jain

C#

// C# programme to find the K'th minimum element
// from an array concatenated M times
using System;
 
class GFG
{
     
// Function to find the K-th minimum element
// from an array concatenated M times
static int KthMinValAfterMconcatenate(int []A, int N,
                                int M, int K)
{
    // Sort the elements in
    // ascending order
    Array.Sort(A);
 
    // Return the K'th Min element
    // present at ( (K-1) / M ) index
    return (A[((K - 1) / M)]);
}
 
// Driver Code
static void Main()
{
    int []A = { 3, 1, 2 };
 
    int M = 3, K = 4;
    int N = A.Length;
 
    Console.WriteLine(KthMinValAfterMconcatenate(A, N, M, K));
}
}
 
// This code is contributed by mits

PHP

<?php
// PHP programme to find the K'th minimum element
// from an array concatenated M times
 
// Function to find the K-th minimum element
// from an array concatenated M times
function KthMinValAfterMconcatenate($A, $N, $M, $K)
{
    // Sort the elements in
    // ascending order
    sort($A);
 
    // Return the K'th Min element
    // present at ( (K-1) / M ) index
    return ($A[(($K - 1) / $M)]);
}
 
// Driver Code
$A = array(3, 1, 2);
 
$M = 3; $K = 4;
$N = sizeof($A);
 
echo(KthMinValAfterMconcatenate($A, $N, $M, $K));
 
// This code contributed by Code_Mech.
?>

Javascript

<script>
 
// JavaScript programme to find the K'th minimum element
// from an array concatenated M times
 
// Function to find the K-th minimum element
// from an array concatenated M times
function KthMinValAfterMconcatenate(A,  N, M,  K)
{
    // Sort the elements in
    // ascending order
    A.sort((a,b)=>a-b)
 
    // Return the K'th Min element
    // present at ( (K-1) / M ) index
    return (A[((K - 1) / M)]);
}
 
// Driver Code
var A = [3, 1, 2 ];
var M = 3, K = 4;
var N = A.length;
document.write( KthMinValAfterMconcatenate(A, N, M, K));
 
 
</script>
Producción

2

Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por Chandan_Agrawal 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 *