Dada una array a[] y un entero N , la tarea es encontrar todos los números naturales del rango [1, N] que no están presentes en la array dada.
Ejemplos:
Entrada: N = 5, a[] = {1, 2, 4, 5}
Salida: 3
Explicación: 3 es el único número entero del rango [1, 5] que no está presente en la array.Entrada: N = 10, a[] = {1, 3, 4, 6, 8, 10}
Salida: 2 5 7 9
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar el rango [1, N] y, para cada número del rango, recorrer la array y verificar si está presente en la array o no.
Complejidad de tiempo: O(N * len), donde len denota la longitud de la array.
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando HashSet . Recorra la array dada e inserte todos los elementos de la array en el HashSet . Luego, recorra el rango [1, N] y para cada elemento, verifique si está presente en HashSet o no usando el método contains() , para calcular la búsqueda en complejidad O(1).
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque alternativo: el problema dado se puede resolver usando BitSet en C++ . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable BitSet , bset con N como longitud.
- Para cada elemento de la array, establezca su bit en falso, usando bset.set(arr[i]-1, 0) , donde establece el bit en la posición arr[i] – 1 a 0 .
- Ahora, itere desde bset._Find_first() a bset.size() – 1 usando una variable, digamos i .
- Imprime i + 1 y configura bset._Find_next() .
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find positive integers // from 1 to N that are not present in the array void findMissingNumbers(int arr[], int len) { const int M = 15; // Declare bitset bitset<M> bset; // Iterate from 0 to M - 1 for (int i = 0; i < M; i++) { bset.set(i); } // Iterate from 0 to len - 1 for (int i = 0; i < len; i++) { bset.set(arr[i] - 1, 0); } // Iterate from bset._Find_first() // to bset.size() - 1 for (int i = bset._Find_first(); i < bset.size(); i = bset._Find_next(i)) { if (i + 1 > len) break; cout << i + 1 << endl; } } // Driver Code int main() { int arr[] = { 1, 2, 4, 6, 8, 9 }; int n = sizeof(arr) / sizeof(arr[0]); findMissingNumbers(arr, n); return 0; }
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to find positive integers // from 1 to N that are not present in the array static void findMissingNumbers(int[] arr, int len) { int M = 15; // Declare bitset BitSet bset = new BitSet(M); // Iterate from 0 to M - 1 for (int i = 0; i < M; i++) { bset.set(i); } // Iterate from 0 to len - 1 for (int i = 0; i < len; i++) { bset.set(arr[i] - 1, false); } // Iterate from bset._Find_first() // to bset.size() - 1 for (int i = bset.nextSetBit(0); i >= 0; i = bset.nextSetBit(i + 1)) { if (i + 1 > len) break; System.out.println(i + 1); } } // Driver Code public static void main(String[] args) { int[] arr = new int[] { 1, 2, 4, 6, 8, 9 }; int n = arr.length; findMissingNumbers(arr, n); } } // This code is contributed by Dharanendra L V
Python3
# Python 3 program for the above approach # Function to find positive integers # from 1 to N that are not present in the array def findMissingNumbers(arr, n): M = 15 # Declare bitset bset = [0]*M # Iterate from 0 to M - 1 for i in range(M): bset[i] = i # Iterate from 0 to n - 1 for i in range(n): bset[arr[i] - 1] = 0 bset = [i for i in bset if i != 0] # Iterate from bset._Find_first() # to bset.size() - 1 for i in range(len(bset)): if (bset[i] + 1 > n): break print(bset[i] + 1) # Driver Code if __name__ == "__main__": arr = [1, 2, 4, 6, 8, 9] n = len(arr) findMissingNumbers(arr, n) # This code is contributed by ukasp.
C#
// C# program for the above approach using System; using System.Collections; class GFG { // Function to find positive integers // from 1 to N that are not present in the array static void findMissingNumbers(int[] arr, int len) { int M = 15; // Declare bitset int[] bset = new int[M]; // Iterate from 0 to M - 1 for (int i = 0; i < M; i++) { bset[i] = i; } // Iterate from 0 to len - 1 for (int i = 0; i < len; i++) { bset[arr[i] - 1] = 0; } ArrayList temp = new ArrayList(); foreach(int x in bset){ if(x != 0){ temp.Add(x); } } // Iterate from bset._Find_first() // to bset.size() - 1 for (int i = 0; i < temp.Count; i++) { if ((int)temp[i] + 1 > len){ break; } Console.WriteLine((int)temp[i] + 1); } } // Driver Code public static void Main() { int[] arr = new int[] { 1, 2, 4, 6, 8, 9 }; int n = arr.Length; findMissingNumbers(arr, n); } } // This code is contributed by Saurabh Jaiswal
Javascript
<script> // JavaScript program for the above approach // Function to find positive integers // from 1 to N that are not present in the array function findMissingNumbers(arr, n){ let M = 15 // Declare bitset let bset = new Array(M).fill(0) // Iterate from 0 to M - 1 for(let i=0;i<M;i++) bset[i] = i // Iterate from 0 to n - 1 for(let i=0;i<n;i++) bset[arr[i] - 1] = 0 bset = bset.filter((i)=>i != 0) // Iterate from bset._Find_first() // to bset.size() - 1 for(let i = 0; i < bset.length; i++) { if (bset[i] + 1 > n) break document.write(bset[i] + 1,"</br>") } } // Driver Code let arr = [1, 2, 4, 6, 8, 9] let n = arr.length findMissingNumbers(arr, n) // This code is contributed by shinjanpatra </script>
3 5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por manupathria y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA