Dada una array arr[] de tamaño N y un entero K , la tarea es encontrar todos los índices en la array dada que tengan al menos K elementos no crecientes antes y K elementos no decrecientes después de ellos.
Ejemplos:
Entrada: arr[] = {1, 1, 1, 1, 1}, K = 0
Salida: 0 1 2 3 4
Explicación: Dado que K es igual a 0, todos los índices satisfacen la condición.Entrada: arr[] = {1, 2, 3, 4, 5, 6}, K = 2
Salida: -1
Explicación: Ningún índice tiene 2 elementos no crecientes antes y 2 elementos no decrecientes después.
Enfoque: la solución se puede encontrar utilizando el concepto de array de prefijos y sufijos. Siga los pasos que se mencionan a continuación:
- Forme la array prefijo[] donde prefijo[i] representa el número de elementos antes de i que obedecen a un orden no creciente .
- Forme la array sufijo[] donde sufijo[i] representa el número de elementos después de i que obedecen a un orden no decreciente .
- Ahora solo los índices deben incluirse en la respuesta para los cuales, tanto el prefijo [i] como el sufijo [i] son mayores o iguales a K .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to find all the indices vector<int> findIndices(int arr[], int K, int N) { vector<int> prefix(N), suffix(N); vector<int> ans; prefix[0] = 0; for (int i = 1; i < N; i++) { if (arr[i] <= arr[i - 1]) prefix[i] = prefix[i - 1] + 1; else prefix[i] = 0; } suffix[N - 1] = 0; for (int i = N - 2; i >= 0; i--) { if (arr[i] <= arr[i + 1]) suffix[i] = suffix[i + 1] + 1; else suffix[i] = 0; } for (int i = 0; i < N; i++) { if (prefix[i] >= K && suffix[i] >= K) ans.push_back(i); } return ans; } // Driver code int main() { int arr[] = { 1, 1, 1, 1, 1 }; int K = 0; int N = sizeof(arr) / sizeof(arr[0]); vector<int> ans = findIndices(arr, K, N); for (int i = 0; i < ans.size(); i++) { cout << ans[i] << " "; } if (ans.size() == 0) cout << "-1"; return 0; }
Java
// Java code for the above approach import java.util.ArrayList; class GFG { // Function to find all the indices static ArrayList<Integer> findIndices(int[] arr, int K, int N) { int[] prefix = new int[N]; int[] suffix = new int[N]; ArrayList<Integer> ans = new ArrayList<Integer>(); prefix[0] = 0; for (int i = 1; i < N; i++) { if (arr[i] <= arr[i - 1]) prefix[i] = prefix[i - 1] + 1; else prefix[i] = 0; } suffix[N - 1] = 0; for (int i = N - 2; i >= 0; i--) { if (arr[i] <= arr[i + 1]) suffix[i] = suffix[i + 1] + 1; else suffix[i] = 0; } for (int i = 0; i < N; i++) { if (prefix[i] >= K && suffix[i] >= K) ans.add(i); } return ans; } // Driver code public static void main(String args[]) { int[] arr = { 1, 1, 1, 1, 1 }; int K = 0; int N = arr.length; ArrayList<Integer> ans = findIndices(arr, K, N); for (int i = 0; i < ans.size(); i++) { System.out.print(ans.get(i) + " "); } if (ans.size() == 0) System.out.println("-1"); } } // This code is contributed by gfgking
Python3
# Python code for the above approach # Function to find all the indices def findIndices (arr, K, N): prefix = [0] * N suffix = [0] * N ans = []; prefix[0] = 0; for i in range(1, N): if (arr[i] <= arr[i - 1]): prefix[i] = prefix[i - 1] + 1; else: prefix[i] = 0; suffix[N - 1] = 0; for i in range(N - 2, 1, -1): if (arr[i] <= arr[i + 1]): suffix[i] = suffix[i + 1] + 1; else: suffix[i] = 0; for i in range(N): if (prefix[i] >= K and suffix[i] >= K): ans.append(i); return ans; # Driver code arr = [1, 1, 1, 1, 1]; K = 0; N = len(arr) ans = findIndices(arr, K, N); for i in range(len(ans)): print(ans[i], end=" "); if (len(ans) == 0): print("-1"); # This code is contributed by Saurabh Jaiswal
C#
// C# code for the above approach using System; using System.Collections.Generic; class GFG { // Function to find all the indices static List<int> findIndices(int[] arr, int K, int N) { int[] prefix = new int[N]; int[] suffix = new int[N]; List<int> ans = new List<int>(); prefix[0] = 0; for (int i = 1; i < N; i++) { if (arr[i] <= arr[i - 1]) prefix[i] = prefix[i - 1] + 1; else prefix[i] = 0; } suffix[N - 1] = 0; for (int i = N - 2; i >= 0; i--) { if (arr[i] <= arr[i + 1]) suffix[i] = suffix[i + 1] + 1; else suffix[i] = 0; } for (int i = 0; i < N; i++) { if (prefix[i] >= K && suffix[i] >= K) ans.Add(i); } return ans; } // Driver code public static void Main() { int[] arr = { 1, 1, 1, 1, 1 }; int K = 0; int N = arr.Length; List<int> ans = findIndices(arr, K, N); for (int i = 0; i < ans.Count; i++) { Console.Write(ans[i] + " "); } if (ans.Count == 0) Console.Write("-1"); } } // This code is contributed by ukasp
Javascript
<script> // JavaScript code for the above approach // Function to find all the indices const findIndices = (arr, K, N) => { let prefix = new Array(N).fill(0); let suffix = new Array(N).fill(0); let ans = []; prefix[0] = 0; for (let i = 1; i < N; i++) { if (arr[i] <= arr[i - 1]) prefix[i] = prefix[i - 1] + 1; else prefix[i] = 0; } suffix[N - 1] = 0; for (let i = N - 2; i >= 0; i--) { if (arr[i] <= arr[i + 1]) suffix[i] = suffix[i + 1] + 1; else suffix[i] = 0; } for (let i = 0; i < N; i++) { if (prefix[i] >= K && suffix[i] >= K) ans.push(i); } return ans; } // Driver code let arr = [1, 1, 1, 1, 1]; let K = 0; let N = arr.length; let ans = findIndices(arr, K, N); for (let i = 0; i < ans.length; i++) { document.write(`${ans[i]} `); } if (ans.length == 0) cout << "-1"; // This code is contributed by rakeshsahni </script>
0 1 2 3 4
Complejidad Temporal: O(N)
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.
Publicación traducida automáticamente
Artículo escrito por sauarbhyadav y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA