Dada una array arr[] de tamaño N donde cada elemento es del rango [0, 9] . La tarea es llegar al último índice de la array a partir del primer índice. Desde el i -ésimo índice podemos pasar a (i – 1) th , (i + 1) th oa cualquier j -ésimo índice donde j ≠ i y arr[j] = arr[i] .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 1, 5}
Salida: 2
Primero muévase del índice 0 al índice 4 y
luego del índice 4 al 5 .Entrada: arr[] = {1, 2, 3, 4, 5, 1}
Salida: 1
Enfoque: construya el gráfico a partir de la array dada donde el número de Nodes en el gráfico será igual al tamaño de la array. Cada Node del grafo i estará conectado al (i 1) th Node, (i + 1) th node y un Node j tal que i ≠ j y arr[i] = arr[j] . Ahora, la respuesta serán los bordes mínimos en el camino del índice 0 al índice N – 1 en el gráfico construido.
El gráfico para la array arr[] = {1, 2, 3, 4, 1, 5} se muestra en la siguiente imagen:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define N 100005 vector<int> gr[N]; // Function to add edge void add_edge(int u, int v) { gr[u].push_back(v); gr[v].push_back(u); } // Function to return the minimum path // from 0th node to the (n - 1)th node int dijkstra(int n) { // To check whether an edge is visited or not // and to keep distance of vertex from 0th index int vis[n] = { 0 }, dist[n]; for (int i = 0; i < n; i++) dist[i] = INT_MAX; // Make 0th index visited and distance is zero vis[0] = 1; dist[0] = 0; // Take a queue and push first element queue<int> q; q.push(0); // Continue this until all vertices are visited while (!q.empty()) { int x = q.front(); // Remove the first element q.pop(); for (int i = 0; i < gr[x].size(); i++) { // Check if a vertex is already visited or not if (vis[gr[x][i]] == 1) continue; // Make vertex visited vis[gr[x][i]] = 1; // Store the number of moves to reach element dist[gr[x][i]] = dist[x] + 1; // Push the current vertex into the queue q.push(gr[x][i]); } } // Return the minimum number of // moves to reach (n - 1)th index return dist[n - 1]; } // Function to return the minimum number of moves // required to reach the end of the array int Min_Moves(int a[], int n) { // To store the positions of each element vector<int> fre[10]; for (int i = 0; i < n; i++) { if (i != n - 1) add_edge(i, i + 1); fre[a[i]].push_back(i); } // Add edge between same elements for (int i = 0; i < 10; i++) { for (int j = 0; j < fre[i].size(); j++) { for (int k = j + 1; k < fre[i].size(); k++) { if (fre[i][j] + 1 != fre[i][k] and fre[i][j] - 1 != fre[i][k]) { add_edge(fre[i][j], fre[i][k]); } } } } // Return the required minimum number of moves return dijkstra(n); } // Driver code int main() { int a[] = { 1, 2, 3, 4, 1, 5 }; int n = sizeof(a) / sizeof(a[0]); cout << Min_Moves(a, n); return 0; }
Java
// Java implementation of the approach import java.io.*; import java.util.*; class GFG{ static ArrayList< ArrayList<Integer>> gr = new ArrayList< ArrayList<Integer>>(); static int N = 100005; // Function to add edge static void add_edge(int u, int v) { for(int i = 0; i < N; i++) { gr.add(new ArrayList<Integer>()); } gr.get(u).add(v); gr.get(v).add(u); } // Function to return the minimum path // from 0th node to the (n - 1)th node static int dijkstra(int n) { // To check whether an edge is visited // or not and to keep distance of // vertex from 0th index int[] vis = new int[n]; Arrays.fill(vis, 0); int[] dist = new int[n]; for(int i = 0; i < n; i++) { dist[i] = Integer.MAX_VALUE; } // Make 0th index visited and // distance is zero vis[0] = 1; dist[0] = 0; // Take a queue and push first element Queue<Integer> q = new LinkedList<>(); q.add(0); // Continue this until all vertices // are visited while (q.size() > 0) { // Remove the first element int x = q.poll(); for(int i = 0; i < gr.get(x).size(); i++) { // Check if a vertex is already // visited or not if (vis[gr.get(x).get(i)] == 1) { continue; } // Make vertex visited vis[gr.get(x).get(i)] = 1; // Store the number of moves to // reach element dist[gr.get(x).get(i)] = dist[x] + 1; // Push the current vertex into // the queue q.add(gr.get(x).get(i)); } } // Return the minimum number of // moves to reach (n - 1)th index return dist[n - 1]; } // Function to return the minimum number of moves // required to reach the end of the array static int Min_Moves(int[] a, int n) { // To store the positions of each element ArrayList< ArrayList<Integer>> fre = new ArrayList< ArrayList<Integer>>(); for(int i = 0; i < 10; i++) { fre.add(new ArrayList<Integer>()); } for(int i = 0; i < n; i++) { if (i != n - 1) { add_edge(i, i + 1); } fre.get(a[i]).add(i); } // Add edge between same elements for(int i = 0; i < 10; i++) { for(int j = 0; j < fre.get(i).size(); j++) { for(int k = j + 1; k < fre.get(i).size(); k++) { if (fre.get(i).get(j) + 1 != fre.get(i).get(k) && fre.get(i).get(j) - 1 != fre.get(i).get(k)) { add_edge(fre.get(i).get(j), fre.get(i).get(k)); } } } } // Return the required minimum // number of moves return dijkstra(n); } // Driver code public static void main(String[] args) { int[] a = { 1, 2, 3, 4, 1, 5 }; int n = a.length; System.out.println(Min_Moves(a, n)); } } // This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation of the approach from collections import deque N = 100005 gr = [[] for i in range(N)] # Function to add edge def add_edge(u, v): gr[u].append(v) gr[v].append(u) # Function to return the minimum path # from 0th node to the (n - 1)th node def dijkstra(n): # To check whether an edge is visited # or not and to keep distance of vertex # from 0th index vis = [0 for i in range(n)] dist = [10**9 for i in range(n)] # Make 0th index visited and # distance is zero vis[0] = 1 dist[0] = 0 # Take a queue and # append first element q = deque() q.append(0) # Continue this until # all vertices are visited while (len(q) > 0): x = q.popleft() # Remove the first element for i in gr[x]: # Check if a vertex is # already visited or not if (vis[i] == 1): continue # Make vertex visited vis[i] = 1 # Store the number of moves # to reach element dist[i] = dist[x] + 1 # Push the current vertex # into the queue q.append(i) # Return the minimum number of # moves to reach (n - 1)th index return dist[n - 1] # Function to return the minimum number of moves # required to reach the end of the array def Min_Moves(a, n): # To store the positions of each element fre = [[] for i in range(10)] for i in range(n): if (i != n - 1): add_edge(i, i + 1) fre[a[i]].append(i) # Add edge between same elements for i in range(10): for j in range(len(fre[i])): for k in range(j + 1,len(fre[i])): if (fre[i][j] + 1 != fre[i][k] and fre[i][j] - 1 != fre[i][k]): add_edge(fre[i][j], fre[i][k]) # Return the required # minimum number of moves return dijkstra(n) # Driver code a = [1, 2, 3, 4, 1, 5] n = len(a) print(Min_Moves(a, n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { static List<List<int>> gr = new List<List<int>>(); static int N = 100005; // Function to add edge static void add_edge(int u, int v) { for(int i = 0; i < N; i++) { gr.Add(new List<int>()); } gr[u].Add(v); gr[v].Add(u); } // Function to return the minimum path // from 0th node to the (n - 1)th node static int dijkstra(int n) { // To check whether an edge is visited // or not and to keep distance of // vertex from 0th index int[] vis = new int[n]; Array.Fill(vis, 0); int[] dist = new int[n]; for(int i = 0; i < n; i++) { dist[i] = Int32.MaxValue; } // Make 0th index visited and // distance is zero vis[0] = 1; dist[0] = 0; // Take a queue and push first element Queue<int> q = new Queue<int>(); q.Enqueue(0); // Continue this until all vertices // are visited while(q.Count > 0) { // Remove the first element int x = q.Dequeue(); for(int i = 0; i < gr[x].Count; i++ ) { // Check if a vertex is already // visited or not if(vis[gr[x][i]] == 1) { continue; } // Make vertex visited vis[gr[x][i]] = 1; // Store the number of moves to // reach element dist[gr[x][i]] = dist[x] + 1; // Push the current vertex into // the queue q.Enqueue(gr[x][i]); } } // Return the minimum number of // moves to reach (n - 1)th index return dist[n - 1]; } // Function to return the minimum number of moves // required to reach the end of the array static int Min_Moves(int[] a, int n) { // To store the positions of each element List<List<int>> fre = new List<List<int>>(); for(int i = 0; i < 10; i++) { fre.Add(new List<int>()); } for(int i = 0; i < n; i++) { if (i != n - 1) { add_edge(i, i + 1); } fre[a[i]].Add(i); } // Add edge between same elements for(int i = 0; i < 10; i++) { for(int j = 0; j < fre[i].Count; j++) { for(int k = j + 1; k < fre[i].Count; k++) { if(fre[i][j] + 1 != fre[i][k] && fre[i][j] - 1 != fre[i][k]) { add_edge(fre[i][j], fre[i][k]); } } } } // Return the required minimum // number of moves return dijkstra(n); } // Driver code static public void Main () { int[] a = { 1, 2, 3, 4, 1, 5 }; int n = a.Length; Console.WriteLine(Min_Moves(a, n)); } } // This code is contributed by rag2127
Javascript
<script> // Javascript implementation of the approach let gr = []; let N = 100005; // Function to add edge function add_edge(u,v) { for(let i = 0; i < N; i++) { gr.push([]); } gr[u].push(v); gr[v].push(u); } // Function to return the minimum path // from 0th node to the (n - 1)th node function dijkstra(n) { // To check whether an edge is visited // or not and to keep distance of // vertex from 0th index let vis = new Array(n); for(let i = 0; i < vis.length; i++) { vis[i] = 0; } let dist = new Array(n); for(let i = 0; i < n; i++) { dist[i] = Number.MAX_VALUE; } // Make 0th index visited and // distance is zero vis[0] = 1; dist[0] = 0; // Take a queue and push first element let q = []; q.push(0); // Continue this until all vertices // are visited while (q.length > 0) { // Remove the first element let x = q.shift(); for(let i = 0; i < gr[x].length; i++) { // Check if a vertex is already // visited or not if (vis[gr[x][i]] == 1) { continue; } // Make vertex visited vis[gr[x][i]] = 1; // Store the number of moves to // reach element dist[gr[x][i]] = dist[x] + 1; // Push the current vertex into // the queue q.push(gr[x][i]); } } // Return the minimum number of // moves to reach (n - 1)th index return dist[n - 1]; } // Function to return the minimum number of moves // required to reach the end of the array function Min_Moves(a,n) { // To store the positions of each element let fre = []; for(let i = 0; i < 10; i++) { fre.push([]); } for(let i = 0; i < n; i++) { if (i != n - 1) { add_edge(i, i + 1); } fre[a[i]].push(i); } // Add edge between same elements for(let i = 0; i < 10; i++) { for(let j = 0; j < fre[i].length; j++) { for(let k = j + 1; k < fre[i].length; k++) { if (fre[i][j] + 1 != fre[i][k] && fre[i][j] - 1 != fre[i][k]) { add_edge(fre[i][j], fre[i][k]); } } } } // Return the required minimum // number of moves return dijkstra(n); } // Driver code let a = [1, 2, 3, 4, 1, 5 ]; let n = a.length; document.write(Min_Moves(a, n)); // This code is contributed by unknown2108 </script>
2
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA