Dadas dos arrays arr[] y jump[] , cada una de longitud N , donde jump[i] denota el número de índices por los que el i -ésimo elemento en la array arr[] puede avanzar, la tarea es encontrar el número mínimo de saltos necesarios para que la array se ordene en orden ascendente .
Nota:
Todos los elementos de la array arr[] son distintos.
Al saltar, los elementos de la array pueden superponerse (es decir, estar en el mismo índice).
Los elementos de la array se pueden mover a los índices que exceden el tamaño de la array .
Ejemplos:
Entrada: arr[] = {3, 1, 2}, jump[] = {1, 4, 5}
Salida: 3
Explicación:
La siguiente secuencia requiere un número mínimo de saltos para clasificar la array en orden ascendente:
Salto 1: arr[ 0] salta de 1 ( = jump[0]) índice a índice 1.
Jump 2: arr[0] salta de 1 ( = jump[0]) índice a índice 2.
Jump 3: arr[0] salta de 1 ( = saltar[0]) índice al índice 3.
Por lo tanto, el número mínimo de operaciones requeridas es 3.Entrada: arr[] = {3, 2, 1}, jump[] = {1, 1, 1}
Salida: 6
Explicación:
La siguiente secuencia requiere un número mínimo de saltos para clasificar la array en orden ascendente:
Salto 1: arr[ 0] salta de 1 ( = jump[0]) índice al índice 1.
Jump 2: arr[0] salta de 1 ( = jump[0]) índice al índice 2.
Jump 3: arr[0] salta de 1 ( = jump[0]) índice al índice 3.
Jump 4: arr[1] salta de 1 ( = jump[0]) índice al índice 2.
Jump 5: arr[1] salta de 1 ( = jump [0]) índice al índice 3.
Saltar 6: arr[0] salta de 1 ( = jump[0]) índice al índice 4.
Por lo tanto, el número mínimo de operaciones requeridas es 6.
Enfoque: El problema dado se puede resolver con avidez . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos jumps = 0 , para almacenar el número mínimo de saltos necesarios.
- Inicialice una array, digamos temp[] , donde temp[arr[i]] almacena la distancia que puede saltar arr[i]
- Inicialice un vector de pares , digamos vect , para almacenar los elementos de la array arr[] y sus respectivos índices, es decir , {arr[i], i + 1}
- Ordenar el vector vector .
- Atraviese el vector vect , sobre el rango de índices [1, N – 1]. Actualice el valor de vect[i] mientras vect[i].segundo ≤ vect[i-1].segundo , agregando la distancia de salto a vect[i].segundo .
- Incrementa los saltos en 1 .
- Imprime el valor de los saltos .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count minimum number
// of jumps required to sort the array
void minJumps(int arr[], int jump[], int N)
{
// Stores minimum number of jumps
int jumps = 0;
// Stores distances of jumps
int temp[1000];
// Stores the array elements
// with their starting indices
vector<pair<int, int> > vect;
// Push the pairs {arr[i], i+1}
// into the vector of pairs vect
for (int i = 0; i < N; i++) {
// Update vect
vect.push_back({ arr[i], i + 1 });
}
// Populate the array temp[]
for (int i = 0; i < N; i++) {
// Update temp[arr[i]]
temp[arr[i]] = jump[i];
}
// Sort the vector in
// the ascending order
sort(vect.begin(), vect.end());
for (int i = 1; i < N; i++) {
// Jump till the previous
// index <= current index
while (vect[i].second <= vect[i - 1].second) {
// Update vect[i]
vect[i] = make_pair(vect[i].first,
vect[i].second
+ temp[vect[i].first]);
// Increment the
// number of jumps
jumps++;
}
}
// Print the minimum number
// of jumps required
cout << jumps << endl;
}
// Driver Code
int main()
{
// Input
int arr[] = { 3, 2, 1 };
int jump[] = { 1, 1, 1 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
minJumps(arr, jump, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to count minimum number
// of jumps required to sort the array
static void minJumps(int arr[], int jump[], int N)
{
// Stores minimum number of jumps
int jumps = 0;
// Stores distances of jumps
int temp[] = new int[1000];
// Stores the array elements
// with their starting indices
int vect[][] = new int[N][2];
// Push the pairs {arr[i], i+1}
// into the vector of pairs vect
for(int i = 0; i < N; i++)
{
// Update vect
vect[i][0] = arr[i];
vect[i][1] = i + 1;
}
// Populate the array temp[]
for(int i = 0; i < N; i++)
{
// Update temp[arr[i]]
temp[arr[i]] = jump[i];
}
// Sort the vector in
// the ascending order
Arrays.sort(vect, (a, b) -> {
if (a[0] != b[0])
return a[0] - b[0];
return a[1] - b[1];
});
for(int i = 1; i < N; i++)
{
// Jump till the previous
// index <= current index
while (vect[i][1] <= vect[i - 1][1])
{
// Update vect[i]
vect[i][0] = vect[i][0];
vect[i][1] = vect[i][1] + temp[vect[i][0]];
// Increment the
// number of jumps
jumps++;
}
}
// Print the minimum number
// of jumps required
System.out.println(jumps);
}
// Driver Code
public static void main(String[] args)
{
// Input
int arr[] = { 3, 2, 1 };
int jump[] = { 1, 1, 1 };
// Size of the array
int N = arr.length;
minJumps(arr, jump, N);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
# Function to count minimum number
# of jumps required to sort the array
def minJumps(arr, jump, N):
# Stores minimum number of jumps
jumps = 0
# Stores distances of jumps
temp = [0 for i in range(1000)]
# Stores the array elements
# with their starting indices
vect = []
# Push the pairs {arr[i], i+1}
# into the vector of pairs vect
for i in range(N):
# Update vect
vect.append([arr[i], i + 1])
# Populate the array temp[]
for i in range(N):
# Update temp[arr[i]]
temp[arr[i]] = jump[i]
# Sort the vector in
# the ascending order
vect.sort(reverse = False)
for i in range(N):
# Jump till the previous
# index <= current index
while (vect[i][1] <= vect[i - 1][1]):
# Update vect[i]
vect[i] = [vect[i][0], vect[i][1] +
temp[vect[i][0]]]
# Increment the
# number of jumps
jumps += 1
# Print the minimum number
# of jumps required
print(jumps)
# Driver Code
if __name__ == '__main__':
# Input
arr = [3, 2, 1]
jump = [1, 1, 1]
# Size of the array
N = len(arr)
minJumps(arr, jump, N)
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
using System.Linq;
using System.Collections.Generic;
class GFG {
public class pair {
public int first, second;
public pair(int first, int second) {
this.first = first;
this.second = second;
}
}
// Function to count minimum number
// of jumps required to sort the array
static void minJumps(int[] arr, int[] jump, int N)
{
// Stores minimum number of jumps
int jumps = 0;
// Stores distances of jumps
int[] temp= new int[1000];
// Stores the array elements
// with their starting indices
List<pair> vect;
vect = new List<pair>();
// Push the pairs {arr[i], i+1}
// into the vector of pairs vect
for(int i = 0; i < N; i++)
{
// Update vect
vect.Add(new pair(arr[i], i+1));
}
// Populate the array temp[]
for (int i = 0; i < N; i++) {
// Update temp[arr[i]]
temp[arr[i]] = jump[i];
}
// Sort the vector in
// the ascending order
vect.Sort((a, b) => { if (a.first != b.first)
return a.first - b.first;
return a.second - b.second; });
for(int i = 1; i < N; i++)
{
// Jump till the previous
// index <= current index
while (vect[i].second <= vect[i - 1].second)
{
// Update vect[i]
vect[i].first = vect[i].first;
vect[i].second = vect[i].second + temp[vect[i].first];
// Increment the
// number of jumps
jumps++;
}
}
// Print the minimum number
// of jumps required
Console.WriteLine(jumps);
}
// Driver program
public static void Main()
{
// Input
int[] arr = new int[] { 3, 2, 1 };
int[] jump = new int[] { 1, 1, 1 };
// Size of the array
int N = arr.Length;
minJumps(arr, jump, N);
}
}
// This code is contributed by Pushpesh Raj.
Javascript
<script>
// JavaScript program for the above approach
// Function to count minimum number
// of jumps required to sort the array
const minJumps = (arr, jump, N) => {
// Stores minimum number of jumps
let jumps = 0;
// Stores distances of jumps
let temp = new Array(1000).fill(0);
// Stores the array elements
// with their starting indices
let vect = [];
// Push the pairs {arr[i], i+1}
// into the vector of pairs vect
for (let i = 0; i < N; i++) {
// Update vect
vect.push([arr[i], i + 1]);
}
// Populate the array temp[]
for (let i = 0; i < N; i++) {
// Update temp[arr[i]]
temp[arr[i]] = jump[i];
}
// Sort the vector in
// the ascending order
vect.sort();
for (let i = 1; i < N; i++) {
// Jump till the previous
// index <= current index
while (vect[i][1] <= vect[i - 1][1]) {
// Update vect[i]
vect[i] = [vect[i][0],
vect[i][1]
+ temp[vect[i][0]]];
// Increment the
// number of jumps
jumps++;
}
}
// Print the minimum number
// of jumps required
document.write(`${jumps}<br/>`);
}
// Driver Code
// Input
let arr = [3, 2, 1];
let jump = [1, 1, 1];
// Size of the array
let N = arr.length;
minJumps(arr, jump, N);
// This code is contributed by rakeshsahni
</script>
6
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA