Dada una array, arr[0..n-1] de elementos distintos y un rango [bajo, alto], encuentra todos los números que están en un rango, pero no la array. Los elementos que faltan deben imprimirse en orden ordenado.
Ejemplos:
Input: arr[] = {10, 12, 11, 15},
low = 10, high = 15
Output: 13, 14
Input: arr[] = {1, 14, 11, 51, 15},
low = 50, high = 55
Output: 50, 52, 53, 54 55
Puede haber dos enfoques para resolver el problema.
Usar clasificación: ordene la array, luego realice una búsqueda binaria de ‘bajo’. Una vez que se encuentra la ubicación del mínimo, comience a recorrer la array desde esa ubicación y siga imprimiendo todos los números que faltan.
Implementación:
C++
// A sorting based C++ program to find missing
// elements from an array
#include <bits/stdc++.h>
using namespace std;
// Print all elements of range [low, high] that
// are not present in arr[0..n-1]
void printMissing(int arr[], int n, int low,
int high)
{
// Sort the array
sort(arr, arr + n);
// Do binary search for 'low' in sorted
// array and find index of first element
// which either equal to or greater than
// low.
int* ptr = lower_bound(arr, arr + n, low);
int index = ptr - arr;
// Start from the found index and linearly
// search every range element x after this
// index in arr[]
int i = index, x = low;
while (i < n && x <= high) {
// If x doesn't match with current element
// print it
if (arr[i] != x)
cout << x << " ";
// If x matches, move to next element in arr[]
else
i++;
// Move to next element in range [low, high]
x++;
}
// Print range elements that are greater than the
// last element of sorted array.
while (x <= high)
cout << x++ << " ";
}
// Driver program
int main()
{
int arr[] = { 1, 3, 5, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int low = 1, high = 10;
printMissing(arr, n, low, high);
return 0;
}
Java
// A sorting based Java program to find missing
// elements from an array
import java.util.Arrays;
public class PrintMissing {
// Print all elements of range [low, high] that
// are not present in arr[0..n-1]
static void printMissing(int ar[], int low, int high)
{
Arrays.sort(ar);
// Do binary search for 'low' in sorted
// array and find index of first element
// which either equal to or greater than
// low.
int index = ceilindex(ar, low, 0, ar.length - 1);
int x = low;
// Start from the found index and linearly
// search every range element x after this
// index in arr[]
while (index < ar.length && x <= high) {
// If x doesn't match with current element
// print it
if (ar[index] != x) {
System.out.print(x + " ");
}
// If x matches, move to next element in arr[]
else
index++;
// Move to next element in range [low, high]
x++;
}
// Print range elements that are greater than the
// last element of sorted array.
while (x <= high) {
System.out.print(x + " ");
x++;
}
}
// Utility function to find ceil index of given element
static int ceilindex(int ar[], int val, int low, int high)
{
if (val < ar[0])
return 0;
if (val > ar[ar.length - 1])
return ar.length;
int mid = (low + high) / 2;
if (ar[mid] == val)
return mid;
if (ar[mid] < val) {
if (mid + 1 < high && ar[mid + 1] >= val)
return mid + 1;
return ceilindex(ar, val, mid + 1, high);
}
else {
if (mid - 1 >= low && ar[mid - 1] < val)
return mid;
return ceilindex(ar, val, low, mid - 1);
}
}
// Driver program to test above function
public static void main(String[] args)
{
int arr[] = { 1, 3, 5, 4 };
int low = 1, high = 10;
printMissing(arr, low, high);
}
}
// This code is contributed by Rishabh Mahrsee
Python3
# Python library for binary search from bisect import bisect_left # A sorting based C++ program to find missing # elements from an array # Print all elements of range [low, high] that # are not present in arr[0..n-1] def printMissing(arr, n, low, high): # Sort the array arr.sort() # Do binary search for 'low' in sorted # array and find index of first element # which either equal to or greater than # low. ptr = bisect_left(arr, low) index = ptr # Start from the found index and linearly # search every range element x after this # index in arr[] i = index x = low while (i < n and x <= high): # If x doesn't match with current element # print it if(arr[i] != x): print(x, end =" ") # If x matches, move to next element in arr[] else: i = i + 1 # Move to next element in range [low, high] x = x + 1 # Print range elements that are greater than the # last element of sorted array. while (x <= high): print(x, end =" ") x = x + 1 # Driver code arr = [1, 3, 5, 4] n = len(arr) low = 1 high = 10 printMissing(arr, n, low, high); # This code is contributed by YatinGupta
C#
// A sorting based Java program to
// find missing elements from an array
using System;
class GFG {
// Print all elements of range
// [low, high] that are not
// present in arr[0..n-1]
static void printMissing(int[] ar,
int low, int high)
{
Array.Sort(ar);
// Do binary search for 'low' in sorted
// array and find index of first element
// which either equal to or greater than
// low.
int index = ceilindex(ar, low, 0,
ar.Length - 1);
int x = low;
// Start from the found index and linearly
// search every range element x after this
// index in arr[]
while (index < ar.Length && x <= high) {
// If x doesn't match with current
// element print it
if (ar[index] != x) {
Console.Write(x + " ");
}
// If x matches, move to next
// element in arr[]
else
index++;
// Move to next element in
// range [low, high]
x++;
}
// Print range elements that
// are greater than the
// last element of sorted array.
while (x <= high) {
Console.Write(x + " ");
x++;
}
}
// Utility function to find
// ceil index of given element
static int ceilindex(int[] ar, int val,
int low, int high)
{
if (val < ar[0])
return 0;
if (val > ar[ar.Length - 1])
return ar.Length;
int mid = (low + high) / 2;
if (ar[mid] == val)
return mid;
if (ar[mid] < val) {
if (mid + 1 < high && ar[mid + 1] >= val)
return mid + 1;
return ceilindex(ar, val, mid + 1, high);
}
else {
if (mid - 1 >= low && ar[mid - 1] < val)
return mid;
return ceilindex(ar, val, low, mid - 1);
}
}
// Driver Code
static public void Main()
{
int[] arr = { 1, 3, 5, 4 };
int low = 1, high = 10;
printMissing(arr, low, high);
}
}
// This code is contributed
// by Sach_Code
Javascript
<script>
// JavaScript code for the above approach
// Print all elements of range [low, high] that
// are not present in arr[0..n-1]
function printMissing(ar, low, high)
{
ar.sort();
// Do binary search for 'low' in sorted
// array and find index of first element
// which either equal to or greater than
// low.
let index = ceilindex(ar, low, 0, ar.length - 1);
let x = low;
// Start from the found index and linearly
// search every range element x after this
// index in arr[]
while (index < ar.length && x <= high) {
// If x doesn't match with current element
// print it
if (ar[index] != x) {
document.write(x + " ");
}
// If x matches, move to next element in arr[]
else
index++;
// Move to next element in range [low, high]
x++;
}
// Print range elements that are greater than the
// last element of sorted array.
while (x <= high) {
document.write(x + " ");
x++;
}
}
// Utility function to find ceil index of given element
function ceilindex(ar, val, low, high)
{
if (val < ar[0])
return 0;
if (val > ar[ar.length - 1])
return ar.length;
let mid = Math.floor((low + high) / 2);
if (ar[mid] == val)
return mid;
if (ar[mid] < val) {
if (mid + 1 < high && ar[mid + 1] >= val)
return mid + 1;
return ceilindex(ar, val, mid + 1, high);
}
else {
if (mid - 1 >= low && ar[mid - 1] < val)
return mid;
return ceilindex(ar, val, low, mid - 1);
}
}
// Driver Code
let arr = [ 1, 3, 5, 4 ];
let low = 1, high = 10;
printMissing(arr, low, high);
</script>
Producción
2 6 7 8 9 10
Complejidad de tiempo: O(n log n + k) donde k es el número de elementos faltantes
Espacio auxiliar: O(n) u O(1) según el tipo de array.
Uso de arrays: cree una array booleana, donde cada índice representará si el elemento (i+low)th está presente en la array o no. Marque todos aquellos elementos que están en el rango dado y están presentes en la array. Una vez que todos los elementos de la array presentes en el rango dado se han marcado como verdaderos en la array, recorremos la array booleana e imprimimos todos los elementos cuyo valor es falso.
Implementación:
C++14
// An array based C++ program
// to find missing elements from
// an array
#include <bits/stdc++.h>
using namespace std;
// Print all elements of range
// [low, high] that are not present
// in arr[0..n-1]
void printMissing(
int arr[], int n,
int low, int high)
{
// Create boolean array of size
// high-low+1, each index i representing
// whether (i+low)th element found or not.
bool points_of_range[high - low + 1] = { false };
for (int i = 0; i < n; i++) {
// if ith element of arr is in
// range low to high then mark
// corresponding index as true in array
if (low <= arr[i] && arr[i] <= high)
points_of_range[arr[i] - low] = true;
}
// Traverse through the range and
// print all elements whose value
// is false
for (int x = 0; x <= high - low; x++) {
if (points_of_range[x] == false)
cout << low + x << " ";
}
}
// Driver program
int main()
{
int arr[] = { 1, 3, 5, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int low = 1, high = 10;
printMissing(arr, n, low, high);
return 0;
}
// This code is contributed by Shubh Bansal
Java
// An array based Java program
// to find missing elements from
// an array
import java.util.Arrays;
public class Print {
// Print all elements of range
// [low, high] that are not present
// in arr[0..n-1]
static void printMissing(
int arr[], int low,
int high)
{
// Create boolean array of
// size high-low+1, each index i
// representing whether (i+low)th
// element found or not.
boolean[] points_of_range = new boolean
[high - low + 1];
for (int i = 0; i < arr.length; i++) {
// if ith element of arr is in
// range low to high then mark
// corresponding index as true in array
if (low <= arr[i] && arr[i] <= high)
points_of_range[arr[i] - low] = true;
}
// Traverse through the range and print all
// elements whose value is false
for (int x = 0; x <= high - low; x++) {
if (points_of_range[x] == false)
System.out.print((low + x) + " ");
}
}
// Driver program to test above function
public static void main(String[] args)
{
int arr[] = { 1, 3, 5, 4 };
int low = 1, high = 10;
printMissing(arr, low, high);
}
}
// This code is contributed by Shubh Bansal
Python3
# An array-based Python3 program to # find missing elements from an array # Print all elements of range # [low, high] that are not # present in arr[0..n-1] def printMissing(arr, n, low, high): # Create boolean list of size # high-low+1, each index i # representing whether (i+low)th # element found or not. points_of_range = [False] * (high-low+1) for i in range(n) : # if ith element of arr is in range # low to high then mark corresponding # index as true in array if ( low <= arr[i] and arr[i] <= high ) : points_of_range[arr[i]-low] = True # Traverse through the range # and print all elements whose value # is false for x in range(high-low+1) : if (points_of_range[x]==False) : print(low+x, end = " ") # Driver Code arr = [1, 3, 5, 4] n = len(arr) low, high = 1, 10 printMissing(arr, n, low, high) # This code is contributed # by Shubh Bansal
C#
// An array based C# program
// to find missing elements from
// an array
using System;
class GFG{
// Print all elements of range
// [low, high] that are not present
// in arr[0..n-1]
static void printMissing(int[] arr, int n,
int low, int high)
{
// Create boolean array of size
// high-low+1, each index i representing
// whether (i+low)th element found or not.
bool[] points_of_range = new bool[high - low + 1];
for(int i = 0; i < high - low + 1; i++)
points_of_range[i] = false;
for(int i = 0; i < n; i++)
{
// If ith element of arr is in
// range low to high then mark
// corresponding index as true in array
if (low <= arr[i] && arr[i] <= high)
points_of_range[arr[i] - low] = true;
}
// Traverse through the range and
// print all elements whose value
// is false
for(int x = 0; x <= high - low; x++)
{
if (points_of_range[x] == false)
Console.Write("{0} ", low + x);
}
}
// Driver code
public static void Main()
{
int[] arr = { 1, 3, 5, 4 };
int n = arr.Length;
int low = 1, high = 10;
printMissing(arr, n, low, high);
}
}
// This code is contributed by subhammahato348
Javascript
<script>
// Javascript program to find missing elements from
// an array
// Print all elements of range
// [low, high] that are not present
// in arr[0..n-1]
function printMissing(
arr, low, high)
{
// Create boolean array of
// size high-low+1, each index i
// representing whether (i+low)th
// element found or not.
let points_of_range = Array(high - low + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
// if ith element of arr is in
// range low to high then mark
// corresponding index as true in array
if (low <= arr[i] && arr[i] <= high)
points_of_range[arr[i] - low] = true;
}
// Traverse through the range and print all
// elements whose value is false
for (let x = 0; x <= high - low; x++) {
if (points_of_range[x] == false)
document.write((low + x) + " ");
}
}
// Driver program
let arr = [ 1, 3, 5, 4 ];
let low = 1, high = 10;
printMissing(arr, low, high);
// This code is contributed by code_hunt.
</script>
Producción
2 6 7 8 9 10
Complejidad de tiempo: O(n + (alto-bajo+1))
Espacio auxiliar: O(n)
Use Hashing: cree una tabla hash e inserte todos los elementos de la array en la tabla hash. Una vez que todos los elementos estén en la tabla hash, recorra el rango e imprima todos los elementos que faltan.
C++
// A hashing based C++ program to find missing
// elements from an array
#include <bits/stdc++.h>
using namespace std;
// Print all elements of range [low, high] that
// are not present in arr[0..n-1]
void printMissing(int arr[], int n, int low,
int high)
{
// Insert all elements of arr[] in set
unordered_set<int> s;
for (int i = 0; i < n; i++)
s.insert(arr[i]);
// Traverse through the range an print all
// missing elements
for (int x = low; x <= high; x++)
if (s.find(x) == s.end())
cout << x << " ";
}
// Driver program
int main()
{
int arr[] = { 1, 3, 5, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int low = 1, high = 10;
printMissing(arr, n, low, high);
return 0;
}
Java
// A hashing based Java program to find missing
// elements from an array
import java.util.Arrays;
import java.util.HashSet;
public class Print {
// Print all elements of range [low, high] that
// are not present in arr[0..n-1]
static void printMissing(int ar[], int low, int high)
{
HashSet<Integer> hs = new HashSet<>();
// Insert all elements of arr[] in set
for (int i = 0; i < ar.length; i++)
hs.add(ar[i]);
// Traverse through the range an print all
// missing elements
for (int i = low; i <= high; i++) {
if (!hs.contains(i)) {
System.out.print(i + " ");
}
}
}
// Driver program to test above function
public static void main(String[] args)
{
int arr[] = { 1, 3, 5, 4 };
int low = 1, high = 10;
printMissing(arr, low, high);
}
}
// This code is contributed by Rishabh Mahrsee
Python3
# A hashing based Python3 program to # find missing elements from an array # Print all elements of range # [low, high] that are not # present in arr[0..n-1] def printMissing(arr, n, low, high): # Insert all elements of # arr[] in set s = set(arr) # Traverse through the range # and print all missing elements for x in range(low, high + 1): if x not in s: print(x, end = ' ') # Driver Code arr = [1, 3, 5, 4] n = len(arr) low, high = 1, 10 printMissing(arr, n, low, high) # This code is contributed # by SamyuktaSHegde
C#
// A hashing based C# program to
// find missing elements from an array
using System;
using System.Collections.Generic;
class GFG {
// Print all elements of range
// [low, high] that are not
// present in arr[0..n-1]
static void printMissing(int[] arr, int n,
int low, int high)
{
// Insert all elements of arr[] in set
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < n; i++) {
s.Add(arr[i]);
}
// Traverse through the range
// an print all missing elements
for (int x = low; x <= high; x++)
if (!s.Contains(x))
Console.Write(x + " ");
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 3, 5, 4 };
int n = arr.Length;
int low = 1, high = 10;
printMissing(arr, n, low, high);
}
}
// This code is contributed by ihritik
Javascript
<script>
// A hashing based Java program to find missing
// elements from an array
// Print all elements of range [low, high] that
// are not present in arr[0..n-1]
function printMissing(ar, low, high) {
let hs = new Set();
// Insert all elements of arr[] in set
for (let i = 0; i < ar.length; i++)
hs.add(ar[i]);
// Traverse through the range an print all
// missing elements
for (let i = low; i <= high; i++) {
if (!hs.has(i)) {
document.write(i + " ");
}
}
}
// Driver program to test above function
let arr = [1, 3, 5, 4];
let low = 1, high = 10;
printMissing(arr, low, high);
// This code is contributed by gfgking
</script>
Producción
2 6 7 8 9 10
me Complejidad: O(n + (alto-bajo+1))
Espacio auxiliar: O(n)
¿Qué enfoque es mejor?
La complejidad temporal del primer enfoque es O(nLogn + k) donde k es el número de elementos faltantes (Tenga en cuenta que k puede ser mayor que n Log n si la array es pequeña y el rango es grande)
La complejidad temporal del segundo y la tercera solución es O(n + (alto-bajo+1)).
Si la array dada tiene casi todos los elementos del rango, es decir, n está cerca del valor de (alto-bajo+1), entonces el segundo y el tercer enfoque son definitivamente mejores ya que no hay un factor Log n. Pero si n es mucho más pequeño que el rango, entonces el primer enfoque es mejor ya que no requiere espacio adicional para el hash. También podemos modificar el primer enfoque para imprimir elementos faltantes adyacentes como rango para ahorrar tiempo. Por ejemplo, si faltan 50, 51, 52, 53, 54, 59, podemos imprimirlos como 50-54, 59 en el primer método. Y si se permite la impresión de esta manera, el primer enfoque toma solo el tiempo O (n Log n). De las soluciones segunda y tercera, la segunda solución es mejor porque la complejidad de tiempo en el peor de los casos de la segunda solución es mejor que la tercera.
Este artículo es una contribución de Piyush Gupta y Shubh Bansal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA