Dado un arreglo arr[] de N elementos y un entero K , la tarea es generar un B[] con las siguientes reglas:
- Copie elementos arr[1…N] , N veces a la array B[] .
- Copie elementos arr[1…N/2] , 2*N veces a la array B[] .
- Copie elementos arr[1…N/4] , 3*N veces a la array B[] .
- Del mismo modo, hasta que no quede ningún elemento para copiar en la array B[].
Finalmente imprima el K -ésimo elemento más pequeño de la array B[] . Si K está fuera de los límites de B[] , devuelva -1 .
Ejemplos:
Entrada: arr[] = {1, 2, 3}, K = 4
Salida: 1
{1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 1, 1, 1, 1, 1 } es la array requerida B[]
{1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3} en la forma ordenada donde
1 es el cuarto elemento más pequeño .
Entrada: arr[] = {2, 4, 5, 1}, K = 13
Salida: 2
Acercarse:
- Mantenga un Count_Array donde debemos almacenar el recuento de veces que aparece cada elemento en la array B[]. Se puede hacer para el rango de elementos sumando el conteo en el índice inicial y restando el mismo conteo en el índice final + 1 ubicación.
- Tome la suma acumulada de la array de conteo.
- Mantenga todos los elementos de arr[] con su recuento en Array B[] junto con sus recuentos y ordénelos según el valor del elemento.
- Recorra el vector y vea qué elemento tiene la K-ésima posición en B[] según sus recuentos individuales.
- Si K está fuera de los límites de B[], devuelve -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the Kth element in B[]
int solve(int Array[], int N, int K)
{
// Initialize the count Array
int count_Arr[N + 1] = { 0 };
int factor = 1;
int size = N;
// Reduce N repeatedly to half its value
while (size) {
int start = 1;
int end = size;
// Add count to start
count_Arr[1] += factor * N;
// Subtract same count after end index
count_Arr[end + 1] -= factor * N;
factor++;
size /= 2;
}
for (int i = 2; i <= N; i++)
count_Arr[i] += count_Arr[i - 1];
// Store each element of Array[] with their count
vector<pair<int, int> > element;
for (int i = 0; i < N; i++) {
element.push_back({ Array[i], count_Arr[i + 1] });
}
// Sort the elements wrt value
sort(element.begin(), element.end());
int start = 1;
for (int i = 0; i < N; i++) {
int end = start + element[i].second - 1;
// If Kth element is in range of element[i]
// return element[i]
if (K >= start && K <= end) {
return element[i].first;
}
start += element[i].second;
}
// If K is out of bound
return -1;
}
// Driver code
int main()
{
int arr[] = { 2, 4, 5, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 13;
cout << solve(arr, N, K);
return 0;
}
Java
// Java implementation of the approach
import java.util.Vector;
class GFG
{
// Pair class implementation to use Pair
static class Pair
{
private int first;
private int second;
Pair(int first, int second)
{
this.first = first;
this.second = second;
}
public int getFirst()
{
return first;
}
public int getSecond()
{
return second;
}
}
// Function to return the Kth element in B[]
static int solve(int[] Array, int N, int K)
{
// Initialize the count Array
int[] count_Arr = new int[N + 2];
int factor = 1;
int size = N;
// Reduce N repeatedly to half its value
while (size > 0)
{
int start = 1;
int end = size;
// Add count to start
count_Arr[1] += factor * N;
// Subtract same count after end index
count_Arr[end + 1] -= factor * N;
factor++;
size /= 2;
}
for (int i = 2; i <= N; i++)
count_Arr[i] += count_Arr[i - 1];
// Store each element of Array[]
// with their count
Vector<Pair> element = new Vector<>();
for (int i = 0; i < N; i++)
{
Pair x = new Pair(Array[i],
count_Arr[i + 1]);
element.add(x);
}
int start = 1;
for (int i = 0; i < N; i++)
{
int end = start + element.elementAt(0).getSecond() - 1;
// If Kth element is in range of element[i]
// return element[i]
if (K >= start && K <= end)
return element.elementAt(i).getFirst();
start += element.elementAt(i).getSecond();
}
// If K is out of bound
return -1;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 2, 4, 5, 1 };
int N = arr.length;
int K = 13;
System.out.println(solve(arr, N, K));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of the approach # Function to return the Kth element in B[] def solve(Array, N, K) : # Initialize the count Array count_Arr = [0]*(N + 2) ; factor = 1; size = N; # Reduce N repeatedly to half its value while (size) : start = 1; end = size; # Add count to start count_Arr[1] += factor * N; # Subtract same count after end index count_Arr[end + 1] -= factor * N; factor += 1; size //= 2; for i in range(2, N + 1) : count_Arr[i] += count_Arr[i - 1]; # Store each element of Array[] with their count element = []; for i in range(N) : element.append(( Array[i], count_Arr[i + 1] )); # Sort the elements wrt value element.sort(); start = 1; for i in range(N) : end = start + element[i][1] - 1; # If Kth element is in range of element[i] # return element[i] if (K >= start and K <= end) : return element[i][0]; start += element[i][1]; # If K is out of bound return -1; # Driver code if __name__ == "__main__" : arr = [ 2, 4, 5, 1 ]; N = len(arr); K = 13; print(solve(arr, N, K)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Pair class implementation to use Pair
public class Pair
{
public int first;
public int second;
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
public int getFirst()
{
return first;
}
public int getSecond()
{
return second;
}
}
// Function to return the Kth element in B[]
static int solve(int[] Array, int N, int K)
{
// Initialize the count Array
int[] count_Arr = new int[N + 2];
int factor = 1;
int size = N;
// Reduce N repeatedly to half its value
while (size > 0)
{
int end = size;
// Add count to start
count_Arr[1] += factor * N;
// Subtract same count after end index
count_Arr[end + 1] -= factor * N;
factor++;
size /= 2;
}
for (int i = 2; i <= N; i++)
count_Arr[i] += count_Arr[i - 1];
// Store each element of Array[]
// with their count
List<Pair> element = new List<Pair>();
for (int i = 0; i < N; i++)
{
Pair x = new Pair(Array[i],
count_Arr[i + 1]);
element.Add(x);
}
int start = 1;
for (int i = 0; i < N; i++)
{
int end = start + element[0].getSecond() - 1;
// If Kth element is in range of element[i]
// return element[i]
if (K >= start && K <= end)
return element[i].getFirst();
start += element[i].getSecond();
}
// If K is out of bound
return -1;
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 2, 4, 5, 1 };
int N = arr.Length;
int K = 13;
Console.WriteLine(solve(arr, N, K));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the Kth element in B[]
function solve(arr, N, K) {
// Initialize the count Array
let count_Arr = new Array(N + 1).fill(0);
let factor = 1;
let size = N;
// Reduce N repeatedly to half its value
while (size) {
let start = 1;
let end = size;
// Add count to start
count_Arr[1] += factor * N;
// Subtract same count after end index
count_Arr[end + 1] -= factor * N;
factor++;
size = Math.floor(size / 2);
}
for (let i = 2; i <= N; i++)
count_Arr[i] += count_Arr[i - 1];
// Store each element of Array[] with their count
let element = [];
for (let i = 0; i < N; i++) {
element.push([arr[i], count_Arr[i + 1]]);
}
// Sort the elements wrt value
element.sort((a, b) => a - b);
let start = 1;
for (let i = 0; i < N; i++) {
let end = start + element[i][1] - 1;
// If Kth element is in range of element[i]
// return element[i]
if (K >= start && K <= end) {
return element[i][0];
}
start += element[i][1];
}
// If K is out of bound
return -1;
}
// Driver code
let arr = [2, 4, 5, 1];
let N = arr.length;
let K = 13;
document.write(solve(arr, N, K));
// This code is contributed by gfgking
</script>
Producción:
2
Complejidad de tiempo: O(N * log N)
Espacio Auxiliar: O(N)