Dada una array 2D de tamaño N que contiene distintas alturas de las personas que están en una cola, y un número correspondiente a cada persona (P) que da el número de personas que son más bajas que P y están paradas frente a P. La tarea es determinar la distancia entre dos personas A y B en el orden real de la altura de las personas.
Ejemplo:
Entrada: A = 6, B = 5, arr[][] = {{5, 0}, {3, 0}, {2, 0},
{6, 4}, {1, 0}, {4, 3}}
Salida: 4
Disposición real de la altura de las personas
{5, 0}, {3, 0}, {2, 0}, {1, 0}, {6, 4}, {4, 3}
Distancia entre 6 y 5 es 4
Entrada: A = 1, B = 3, arr[][] = {{3, 0}, {1, 0}, {2, 1}};
Salida: 1
Enfoque ingenuo: un enfoque de fuerza bruta consiste en probar todas las permutaciones posibles de las alturas dadas del orden de los miembros del fénix y verificar si los números del frente coinciden con la secuencia dada, luego encontrar la distancia entre dos personas.
Complejidad de tiempo: O(N!)
Enfoque eficiente: otro enfoque es almacenar la altura de la persona y su valor frontal, almacenarlo en cualquier vector y ordenar el vector según las alturas en orden ascendente. Ahora, atraviese el vector e inserte la persona en la posición k-ésima en el vector de posición donde k es el número de personas que están de pie frente a las personas de la persona actual.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to find the correct order and then // return the distance between the two persons int getDistance(int arr[][2], int n, int a, int b) { vector<pair<int, int> > vp; // Make pair of both height & infront // and insert to vector for (int i = 0; i < n; i++) { vp.push_back({ arr[i][0], arr[i][1] }); } // Sort the vector in ascending order sort(vp.begin(), vp.end()); // Find the correct place for every person vector<int> pos; // Insert into position vector // according to infront value for (int i = 0; i < vp.size(); i++) { int height = vp[i].first; int k = vp[i].second; pos.insert(pos.begin() + k, height); } int first = -1, second = -1; for (int i = 0; i < pos.size(); i++) { if (pos[i] == a) first = i; if (pos[i] == b) second = i; } return abs(first - second); } // Driver code int main() { int arr[][2] = { { 5, 0 }, { 3, 0 }, { 2, 0 }, { 6, 4 }, { 1, 0 }, { 4, 3 } }; int n = sizeof(arr) / sizeof(arr[0]); int a = 6, b = 5; cout << getDistance(arr, n, a, b); return 0; }
Python
# Python implementation of the approach # Function to find the correct order and then # return the distance between the two persons def getDistance(arr, n, a, b): vp = [] # Make pair of both height & infront # and insert to vector for i in range(n): vp.append([arr[i][0], arr[i][1]]) # Sort the vector in ascending order vp = sorted(vp) # Find the correct place for every person pos = [0 for i in range(n)] # Insert into position vector # according to infront value for i in range(len(vp)): height = vp[i][0] k = vp[i][1] pos[k] = height first = -1 second = -1 for i in range(n): if (pos[i] == a): first = i if (pos[i] == b): second = i return abs(first - second) # Driver code arr = [[5, 0], [3, 0], [2, 0], [6, 4], [1, 0], [4, 3]] n = len(arr) a = 6 b = 5 print(getDistance(arr, n, a, b)) # This code is contributed by mohit kumar 29
Javascript
<script> // Javascript implementation of the approach // Function to find the correct order and then // return the distance between the two persons function getDistance(arr,n,a,b) { let vp=[]; // Make pair of both height & infront // and insert to vector for (let i = 0; i < n; i++) { vp.push([ arr[i][0], arr[i][1] ]); } // Sort the vector in ascending order vp.sort(function(c,d){return c[0]-d[0];}); // Find the correct place for every person let pos=new Array(n); for(let i=0;i<n;i++) { pos[i]=0; } // Insert into position vector // according to infront value for (let i = 0; i < vp.length; i++) { let height = vp[i][0]; let k = vp[i][1]; pos[k] = height } let first = -1, second = -1; for (let i = 0; i < pos.length; i++) { if (pos[i] == a) first = i; if (pos[i] == b) second = i; } return Math.abs(first - second); } // Driver code let arr = [ [ 5, 0 ], [ 3, 0 ], [ 2, 0 ], [ 6, 4 ], [ 1, 0 ], [ 4, 3 ] ]; let n = arr.length; let a = 6, b = 5; document.write(getDistance(arr, n, a, b)); // This code is contributed by unknown2108 </script>
4
Complejidad temporal: O(n 2 )
Publicación traducida automáticamente
Artículo escrito por pratyushranjan14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA