Dada una permutación P de primeros N números naturales. La tarea es encontrar el número de i tal que P i ≤ P j para todo 1 ≤ j ≤ i en la permutación de los primeros N números naturales.
Ejemplos:
Entrada: arr[] = {4, 2, 5, 1, 3}
Salida: 3
0, 1 y 3 son tales índices.
Entrada: arr[] = {4, 3, 2, 1}
Salida: 4
Enfoque: Para i = 1, …, N , defina METRO i = min{ PAGS j , 1 ≤ j ≤ i} . Ahora, cuando i(1 ≤ i ≤ N) es fijo, M i = P i se cumple si y solo si para todo j(1 ≤ j ≤ i), P i ≤ P j se cumple. Por tanto, basta con calcular todos los M i . Estos se pueden calcular en orden creciente de i , por lo que el problema podría resolverse en un tiempo total de O(N) .
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 number of i's // such that Pi <= Pj for all 1 <= j <= i // in the permutation of first N natural numbers int min_index(int p[], int n) { // To store the count of such indices int ans = 0; // Store the mini value int mini = INT_MAX; // For all the elements for (int i = 0; i < n; i++) { if (p[i] <= mini) mini = p[i]; if (mini == p[i]) ans++; } // Return the required answer return ans; } // Driver code int main() { int P[] = { 4, 2, 5, 1, 3 }; int n = sizeof(P) / sizeof(int); cout << min_index(P, n); return 0; }
Java
// Java implementation of the approach class GFG { static int INT_MAX = Integer.MAX_VALUE; // Function to return the number of i's // such that Pi <= Pj for all 1 <= j <= i // in the permutation of first N natural numbers static int min_index(int p[], int n) { // To store the count of such indices int ans = 0; // Store the mini value int mini = INT_MAX; // For all the elements for (int i = 0; i < n; i++) { if (p[i] <= mini) mini = p[i]; if (mini == p[i]) ans++; } // Return the required answer return ans; } // Driver code public static void main (String[] args) { int P[] = { 4, 2, 5, 1, 3 }; int n = P.length; System.out.println(min_index(P, n)); } } // This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach import sys INT_MAX = sys.maxsize # Function to return the number of i's # such that Pi <= Pj for all 1 <= j <= i # in the permutation of first N natural numbers def min_index(p, n) : # To store the count of such indices ans = 0; # Store the mini value mini = INT_MAX; # For all the elements for i in range(n) : if (p[i] <= mini) : mini = p[i]; if (mini == p[i]) : ans += 1; # Return the required answer return ans; # Driver code if __name__ == "__main__" : P = [ 4, 2, 5, 1, 3 ]; n = len(P); print(min_index(P, n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach using System; class GFG { static int INT_MAX = int.MaxValue; // Function to return the number of i's // such that Pi <= Pj for all 1 <= j <= i // in the permutation of first N natural numbers static int min_index(int []p, int n) { // To store the count of such indices int ans = 0; // Store the mini value int mini = INT_MAX; // For all the elements for (int i = 0; i < n; i++) { if (p[i] <= mini) mini = p[i]; if (mini == p[i]) ans++; } // Return the required answer return ans; } // Driver code public static void Main () { int []P = { 4, 2, 5, 1, 3 }; int n = P.Length; Console.WriteLine(min_index(P, n)); } } // This code is contributed by AnkitRai01
Javascript
<script> // JavaScript implementation of the approach // Function to return the number of i's // such that Pi <= Pj for all 1 <= j <= i // in the permutation of first N natural numbers function min_index(p, n) { // To store the count of such indices let ans = 0; // Store the mini value let mini = Number.MAX_SAFE_INTEGER; // For all the elements for (let i = 0; i < n; i++) { if (p[i] <= mini) mini = p[i]; if (mini == p[i]) ans++; } // Return the required answer return ans; } // Driver code let P = [ 4, 2, 5, 1, 3 ]; let n = P.length; document.write(min_index(P, n)); // This code is contributed by Manoj. </script>
3
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
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