Dada una array desordenada con elementos positivos y negativos. Encuentre el número positivo más pequeño que falta en la array en tiempo O(n) usando un espacio extra constante. Se permite modificar la array original.
Ejemplos:
Input: {2, 3, 7, 6, 8, -1, -10, 15}
Output: 1
Input: { 2, 3, -7, 6, 8, 1, -10, 15 }
Output: 4
Input: {1, 1, 0, -1, -2}
Output: 2
Hemos discutido una solución de tiempo O (n) y espacio adicional O (1) en la publicación anterior . En este post, se discute otra solución alternativa.
Hacemos que el valor en el índice correspondiente al elemento de array dado sea igual a un elemento de array. Por ejemplo: considere la array = {2, 3, 7, 6, 8, -1, -10, 15}. Para marcar la presencia del elemento 2 en esta array, hacemos arr[2-1] = 2. En el subíndice de array [2-1], 2 es el elemento a marcar y 1 se resta porque estamos mapeando un rango de valores de elementos [1, N] en el rango de valores de índice [0, N-1]. Pero si hacemos arr[1] = 2, perderemos los datos almacenados en arr[1]. Para evitar esto, primero almacenamos el valor presente en arr[1] y luego lo actualizamos. A continuación, marcaremos la presencia del elemento previamente presente en arr[1], es decir, 3. Claramente, esto conduce a algún tipo de recorrido aleatorio sobre la array. Ahora tenemos que especificar una condición para marcar el final de este recorrido. Hay tres condiciones que marcan el final de este recorrido:
1. Si el elemento a marcar es negativo: No es necesario marcar la presencia de este elemento ya que nos interesa encontrar el primer entero positivo que falta. Entonces, si se encuentra un elemento negativo, simplemente finalice el recorrido ya que no se marca más la presencia de un elemento.
2. Si el elemento a marcar es mayor que N: No es necesario marcar la presencia de este elemento porque si este elemento está presente, ciertamente ha ocupado el lugar de un elemento en el rango [1, N] en una array de tamaño N y, por lo tanto, garantizar que nuestra respuesta se encuentre en el rango [1, N]. Así que simplemente finalice el recorrido ya que no se marca más la presencia de un elemento.
3. Si la presencia del elemento actual ya está marcada: Supongamos que el elemento a marcar como presente es val. Si arr[val-1] = val, entonces ya hemos marcado la presencia de este elemento. Así que simplemente finalice el recorrido ya que no se marca más la presencia de un elemento.
También tenga en cuenta que es posible que todos los elementos de una array en el rango [1, N] no estén marcados como presentes en el recorrido actual. Para asegurarnos de que todos los elementos en el rango estén marcados como presentes, verificamos cada elemento de la array que se encuentra en este rango. Si el elemento no está marcado, comenzamos un nuevo recorrido a partir de ese elemento de la array.
Después de haber marcado la presencia de todos los elementos de la array que se encuentran en el rango [1, N], verificamos qué valor de índice ind no es igual a ind+1. Si arr[ind] no es igual a ind+1, entonces ind+1 es el número faltante positivo más pequeño. Recuerde que estamos asignando el rango de valores del índice [0, N-1] al rango de valores del elemento [1, N], por lo que se agrega 1 a ind. Si no se encuentra tal ind, entonces todos los elementos en el rango [1, N] están presentes en la array. Así que el primer número positivo que falta es N+1.
¿Cómo funciona esta solución en tiempo O(n)?
Observe que cada elemento en el rango [1, N] se recorre como máximo dos veces en el peor de los casos. Primero, mientras realizaba un recorrido partió de algún otro elemento en el rango. En segundo lugar, al verificar si se requiere iniciar un nuevo recorrido desde este elemento para marcar la presencia de elementos no marcados. En el peor de los casos, cada elemento en el rango [1, N] está presente en la array y, por lo tanto, todos los N elementos se recorren dos veces. Entonces, los cálculos totales son 2*n y, por lo tanto, la complejidad del tiempo es O(n).
A continuación se muestra la implementación del enfoque anterior:
C++
/* CPP program to find the smallest
positive missing number */
#include <bits/stdc++.h>
using namespace std;
// Function to find smallest positive
// missing number.
int findMissingNo(int arr[], int n)
{
// to store current array element
int val;
// to store next array element in
// current traversal
int nextval;
for (int i = 0; i < n; i++) {
// if value is negative or greater
// than array size, then it cannot
// be marked in array. So move to
// next element.
if (arr[i] <= 0 || arr[i] > n)
continue;
val = arr[i];
// traverse the array until we
// reach at an element which
// is already marked or which
// could not be marked.
while (arr[val - 1] != val) {
nextval = arr[val - 1];
arr[val - 1] = val;
val = nextval;
if (val <= 0 || val > n)
break;
}
}
// find first array index which is
// not marked which is also the
// smallest positive missing
// number.
for (int i = 0; i < n; i++) {
if (arr[i] != i + 1) {
return i + 1;
}
}
// if all indices are marked, then
// smallest missing positive
// number is array_size + 1.
return n + 1;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 7, 6, 8, -1, -10, 15 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
int missing = findMissingNo(arr, arr_size);
cout << "The smallest positive missing number is "
<< missing;
return 0;
}
Java
/* Java program to find the smallest
positive missing number */
import java.io.*;
class GFG {
// Function to find smallest positive
// missing number.
static int findMissingNo(int []arr, int n)
{
// to store current array element
int val;
// to store next array element in
// current traversal
int nextval;
for (int i = 0; i < n; i++) {
// if value is negative or greater
// than array size, then it cannot
// be marked in array. So move to
// next element.
if (arr[i] <= 0 || arr[i] > n)
continue;
val = arr[i];
// traverse the array until we
// reach at an element which
// is already marked or which
// could not be marked.
while (arr[val - 1] != val) {
nextval = arr[val - 1];
arr[val - 1] = val;
val = nextval;
if (val <= 0 || val > n)
break;
}
}
// find first array index which is
// not marked which is also the
// smallest positive missing
// number.
for (int i = 0; i < n; i++) {
if (arr[i] != i + 1) {
return i + 1;
}
}
// if all indices are marked, then
// smallest missing positive
// number is array_size + 1.
return n + 1;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 2, 3, 7, 6, 8, -1, -10, 15 };
int arr_size = arr.length;
int missing = findMissingNo(arr, arr_size);
System.out.println( "The smallest positive"
+ " missing number is " + missing);
}
}
// This code is contributed by anuj_67.
Python 3
# Python 3 program to find the smallest # positive missing number # Function to find smallest positive # missing number. def findMissingNo(arr, n): # to store current array element # to store next array element in # current traversal for i in range(n) : # if value is negative or greater # than array size, then it cannot # be marked in array. So move to # next element. if (arr[i] <= 0 or arr[i] > n): continue val = arr[i] # traverse the array until we # reach at an element which # is already marked or which # could not be marked. while (arr[val - 1] != val): nextval = arr[val - 1] arr[val - 1] = val val = nextval if (val <= 0 or val > n): break # find first array index which is # not marked which is also the # smallest positive missing # number. for i in range(n): if (arr[i] != i + 1) : return i + 1 # if all indices are marked, then # smallest missing positive # number is array_size + 1. return n + 1 # Driver code if __name__ == "__main__": arr = [ 2, 3, 7, 6, 8, -1, -10, 15 ] arr_size = len(arr) missing = findMissingNo(arr, arr_size) print( "The smallest positive", "missing number is ", missing) # This code is contributed # by ChitraNayal
C#
/* C# program to find the smallest
positive missing number */
using System;
class GFG
{
// Function to find smallest
// positive missing number.
static int findMissingNo(int []arr,
int n)
{
// to store current
// array element
int val;
// to store next array element
// in current traversal
int nextval;
for (int i = 0; i < n; i++)
{
// if value is negative or greater
// than array size, then it cannot
// be marked in array. So move to
// next element.
if (arr[i] <= 0 || arr[i] > n)
continue;
val = arr[i];
// traverse the array until we
// reach at an element which
// is already marked or which
// could not be marked.
while (arr[val - 1] != val)
{
nextval = arr[val - 1];
arr[val - 1] = val;
val = nextval;
if (val <= 0 || val > n)
break;
}
}
// find first array index which
// is not marked which is also
// the smallest positive missing
// number.
for (int i = 0; i < n; i++)
{
if (arr[i] != i + 1)
{
return i + 1;
}
}
// if all indices are marked,
// then smallest missing
// positive number is
// array_size + 1.
return n + 1;
}
// Driver code
public static void Main (String[] args)
{
int []arr = {2, 3, 7, 6,
8, -1, -10, 15};
int arr_size = arr.Length;
int missing = findMissingNo(arr, arr_size);
Console.Write("The smallest positive" +
" missing number is " +
missing);
}
}
// This code is contributed
// by shiv_bhakt.
PHP
<?php
// PHP program to find
// the smallest positive
// missing number
// Function to find smallest
// positive missing number.
function findMissingNo($arr, $n)
{
// to store current
// array element
$val;
// to store next array element
// in current traversal
$nextval;
for ($i = 0; $i < $n; $i++)
{
// if value is negative or
// greater than array size,
// then it cannot be marked
// in array. So move to
// next element.
if ($arr[$i] <= 0 ||
$arr[$i] > $n)
continue;
$val = $arr[$i];
// traverse the array until
// we reach at an element
// which is already marked
// or which could not be marked.
while ($arr[$val - 1] != $val)
{
$nextval = $arr[$val - 1];
$arr[$val - 1] = $val;
$val = $nextval;
if ($val <= 0 ||
$val > $n)
break;
}
}
// find first array index
// which is not marked
// which is also the smallest
// positive missing number.
for ($i = 0; $i < $n; $i++)
{
if ($arr[$i] != $i + 1)
{
return $i + 1;
}
}
// if all indices are marked,
// then smallest missing
// positive number is
// array_size + 1.
return $n + 1;
}
// Driver code
$arr = array(2, 3, 7, 6, 8,
-1, -10, 15);
$arr_size = sizeof($arr) /
sizeof($arr[0]);
$missing = findMissingNo($arr,
$arr_size);
echo "The smallest positive " .
"missing number is " ,
$missing;
// This code is contributed
// by shiv_bhakt.
?>
Javascript
<script>
/* Javascript program to find the smallest
positive missing number */
// Function to find smallest positive
// missing number.
function findMissingNo(arr, n)
{
// to store current array element
var val;
// to store next array element in
// current traversal
var nextval;
for (var i = 0; i < n; i++) {
// if value is negative or greater
// than array size, then it cannot
// be marked in array. So move to
// next element.
if (arr[i] <= 0 || arr[i] > n)
continue;
val = arr[i];
// traverse the array until we
// reach at an element which
// is already marked or which
// could not be marked.
while (arr[val - 1] != val) {
nextval = arr[val - 1];
arr[val - 1] = val;
val = nextval;
if (val <= 0 || val > n)
break;
}
}
// find first array index which is
// not marked which is also the
// smallest positive missing
// number.
for (var i = 0; i < n; i++) {
if (arr[i] != i + 1) {
return i + 1;
}
}
// if all indices are marked, then
// smallest missing positive
// number is array_size + 1.
return n + 1;
}
// Driver code
var arr = [ 2, 3, 7, 6, 8, -1, -10, 15 ];
var arr_size = arr.length;
var missing = findMissingNo(arr, arr_size);
document.write( "The smallest positive missing number is "
+ missing);
</script>
The smallest positive missing number is 1
Complejidad temporal: O(n)
Espacio auxiliar: O(1)