Se le da una array desordenada con elementos positivos y negativos. Tienes que encontrar el número positivo más pequeño que falta en la array en tiempo O(n) usando un espacio extra constante. Puede 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
Un método ingenuo para resolver este problema es buscar todos los enteros positivos, comenzando desde 1 en la array dada. Es posible que tengamos que buscar como máximo n+1 números en la array dada. Entonces, esta solución toma O (n ^ 2) en el peor de los casos.
Podemos usar la clasificación para resolverlo en menor complejidad de tiempo. Podemos ordenar la array en tiempo O (nLogn). Una vez que se ordena la array, todo lo que tenemos que hacer es un escaneo lineal de la array. Entonces, este enfoque toma el tiempo O (nLogn + n), que es O (nLogn).
También podemos usar hash . Podemos construir una tabla hash de todos los elementos positivos en la array dada. Una vez construida la tabla hash. Podemos buscar en la tabla hash todos los enteros positivos, comenzando desde 1. Tan pronto como encontramos un número que no está en la tabla hash, lo devolvemos. Este enfoque puede tomar O(n) tiempo en promedio, pero requiere O(n) espacio extra.
Solución de tiempo AO(n) y espacio extra O(1):
La idea es similar a esta publicación. Usamos elementos de array como índice. Para marcar la presencia de un elemento x, cambiamos el valor en el índice x a negativo . Pero este enfoque no funciona si hay números no positivos (-ve y 0). Así que separamos los números positivos de los negativos como primer paso y luego aplicamos el enfoque.
El siguiente es el algoritmo de dos pasos.
1) Separe los números positivos de los demás, es decir, mueva todos los números no positivos al lado izquierdo. En el siguiente código, la función segregar() hace esta parte.
2) Ahora podemos ignorar los elementos no positivos y considerar solo la parte de la array que contiene todos los elementos positivos. Atravesamos la array que contiene todos los números positivos y para marcar la presencia de un elemento x, cambiamos el signo del valor en el índice x a negativo. Atravesamos la array nuevamente e imprimimos el primer índice que tiene un valor positivo . En el siguiente código, la función findMissingPositive() hace esta parte. Tenga en cuenta que en findMissingPositive, hemos restado 1 de los valores ya que los índices comienzan desde 0 en C.
C++
/* C++ program to find the
smallest positive missing number */
#include <bits/stdc++.h>
using namespace std;
/* Utility to swap to integers */
void swap(int* a, int* b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
/* Utility function that puts all
non-positive (0 and negative) numbers on left
side of arr[] and return count of such numbers */
int segregate(int arr[], int size)
{
int j = 0, i;
for (i = 0; i < size; i++) {
if (arr[i] <= 0) {
swap(&arr[i], &arr[j]);
// increment count of
// non-positive integers
j++;
}
}
return j;
}
/* Find the smallest positive missing number
in an array that contains all positive integers */
int findMissingPositive(int arr[], int size)
{
int i;
// Mark arr[i] as visited by
// making arr[arr[i] - 1] negative.
// Note that 1 is subtracted
// because index start
// from 0 and positive numbers start from 1
for (i = 0; i < size; i++) {
if (abs(arr[i]) - 1 < size && arr[abs(arr[i]) - 1] > 0)
arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];
}
// Return the first index
// value at which is positive
for (i = 0; i < size; i++)
if (arr[i] > 0)
// 1 is added because
// indexes start from 0
return i + 1;
return size + 1;
}
/* Find the smallest positive missing
number in an array that contains
both positive and negative integers */
int findMissing(int arr[], int size)
{
// First separate positive
// and negative numbers
int shift = segregate(arr, size);
// Shift the array and call
// findMissingPositive for
// positive part
return findMissingPositive(arr + shift,
size - shift);
}
// Driver code
int main()
{
int arr[] = { 0, 10, 2, -10, -20 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
int missing = findMissing(arr, arr_size);
cout << "The smallest positive missing number is " << missing;
return 0;
}
// This is code is contributed by rathbhupendra
C
/* C program to find the smallest
positive missing number */
#include <stdio.h>
#include <stdlib.h>
/* Utility to swap to integers */
void swap(int* a, int* b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
/* Utility function that puts all
non-positive (0 and negative) numbers on left
side of arr[] and return count of such numbers */
int segregate(int arr[], int size)
{
int j = 0, i;
for (i = 0; i < size; i++) {
if (arr[i] <= 0) {
swap(&arr[i], &arr[j]);
j++; // increment count of non-positive integers
}
}
return j;
}
/* Find the smallest positive missing number
in an array that contains all positive integers */
int findMissingPositive(int arr[], int size)
{
int i;
// Mark arr[i] as visited by
// making arr[arr[i] - 1] negative.
// Note that 1 is subtracted
// because index start
// from 0 and positive numbers start from 1
for (i = 0; i < size; i++) {
if (abs(arr[i]) - 1 < size && arr[abs(arr[i]) - 1] > 0)
arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];
}
// Return the first index value at which is positive
for (i = 0; i < size; i++)
if (arr[i] > 0)
// 1 is added because indexes start from 0
return i + 1;
return size + 1;
}
/* Find the smallest positive missing
number in an array that contains
both positive and negative integers */
int findMissing(int arr[], int size)
{
// First separate positive and negative numbers
int shift = segregate(arr, size);
// Shift the array and call findMissingPositive for
// positive part
return findMissingPositive(arr + shift, size - shift);
}
// Driver code
int main()
{
int arr[] = { 0, 10, 2, -10, -20 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
int missing = findMissing(arr, arr_size);
printf("The smallest positive missing number is %d ", missing);
getchar();
return 0;
}
Java
// Java program to find the smallest
// positive missing number
import java.util.*;
class Main {
/* Utility function that puts all non-positive
(0 and negative) numbers on left side of
arr[] and return count of such numbers */
static int segregate(int arr[], int size)
{
int j = 0, i;
for (i = 0; i < size; i++) {
if (arr[i] <= 0) {
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// increment count of non-positive
// integers
j++;
}
}
return j;
}
/* Find the smallest positive missing
number in an array that contains
all positive integers */
static int findMissingPositive(int arr[], int size)
{
int i;
// Mark arr[i] as visited by making
// arr[arr[i] - 1] negative. Note that
// 1 is subtracted because index start
// from 0 and positive numbers start from 1
for (i = 0; i < size; i++) {
int x = Math.abs(arr[i]);
if (x - 1 < size && arr[x - 1] > 0)
arr[x - 1] = -arr[x - 1];
}
// Return the first index value at which
// is positive
for (i = 0; i < size; i++)
if (arr[i] > 0)
return i + 1; // 1 is added because indexes
// start from 0
return size + 1;
}
/* Find the smallest positive missing
number in an array that contains
both positive and negative integers */
static int findMissing(int arr[], int size)
{
// First separate positive and
// negative numbers
int shift = segregate(arr, size);
int arr2[] = new int[size - shift];
int j = 0;
for (int i = shift; i < size; i++) {
arr2[j] = arr[i];
j++;
}
// Shift the array and call
// findMissingPositive for
// positive part
return findMissingPositive(arr2, j);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 0, 10, 2, -10, -20 };
int arr_size = arr.length;
int missing = findMissing(arr, arr_size);
System.out.println("The smallest positive missing number is " + missing);
}
}
Python3
''' Python3 program to find the
smallest positive missing number '''
''' Utility function that puts all
non-positive (0 and negative) numbers on left
side of arr[] and return count of such numbers '''
def segregate(arr, size):
j = 0
for i in range(size):
if (arr[i] <= 0):
arr[i], arr[j] = arr[j], arr[i]
j += 1 # increment count of non-positive integers
return j
''' Find the smallest positive missing number
in an array that contains all positive integers '''
def findMissingPositive(arr, size):
# Mark arr[i] as visited by
# making arr[arr[i] - 1] negative.
# Note that 1 is subtracted
# because index start
# from 0 and positive numbers start from 1
for i in range(size):
if (abs(arr[i]) - 1 < size and arr[abs(arr[i]) - 1] > 0):
arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]
# Return the first index value at which is positive
for i in range(size):
if (arr[i] > 0):
# 1 is added because indexes start from 0
return i + 1
return size + 1
''' Find the smallest positive missing
number in an array that contains
both positive and negative integers '''
def findMissing(arr, size):
# First separate positive and negative numbers
shift = segregate(arr, size)
# Shift the array and call findMissingPositive for
# positive part
return findMissingPositive(arr[shift:], size - shift)
# Driver code
arr = [ 0, 10, 2, -10, -20 ]
arr_size = len(arr)
missing = findMissing(arr, arr_size)
print("The smallest positive missing number is ", missing)
# This code is contributed by Shubhamsingh10
C#
// C# program to find the smallest
// positive missing number
using System;
class main {
// Utility function that puts all
// non-positive (0 and negative)
// numbers on left side of arr[]
// and return count of such numbers
static int segregate(int[] arr, int size)
{
int j = 0, i;
for (i = 0; i < size; i++) {
if (arr[i] <= 0) {
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// increment count of non-positive
// integers
j++;
}
}
return j;
}
// Find the smallest positive missing
// number in an array that contains
// all positive integers
static int findMissingPositive(int[] arr, int size)
{
int i;
// Mark arr[i] as visited by making
// arr[arr[i] - 1] negative. Note that
// 1 is subtracted as index start from
// 0 and positive numbers start from 1
for (i = 0; i < size; i++) {
if (Math.Abs(arr[i]) - 1 < size && arr[ Math.Abs(arr[i]) - 1] > 0)
arr[ Math.Abs(arr[i]) - 1] = -arr[ Math.Abs(arr[i]) - 1];
}
// Return the first index value at
// which is positive
for (i = 0; i < size; i++)
if (arr[i] > 0)
return i + 1;
// 1 is added because indexes
// start from 0
return size + 1;
}
// Find the smallest positive
// missing number in array that
// contains both positive and
// negative integers
static int findMissing(int[] arr, int size)
{
// First separate positive and
// negative numbers
int shift = segregate(arr, size);
int[] arr2 = new int[size - shift];
int j = 0;
for (int i = shift; i < size; i++) {
arr2[j] = arr[i];
j++;
}
// Shift the array and call
// findMissingPositive for
// positive part
return findMissingPositive(arr2, j);
}
// Driver code
public static void Main()
{
int[] arr = { 0, 10, 2, -10, -20 };
int arr_size = arr.Length;
int missing = findMissing(arr, arr_size);
Console.WriteLine("The smallest positive missing number is " + missing);
}
}
// This code is contributed by Anant Agarwal.
Javascript
<script>
// Javascript program to find the smallest
// positive missing number
/* Utility function that puts all non-positive
(0 and negative) numbers on left side of
arr[] and return count of such numbers */
function segregate(arr,size)
{
let j = 0, i;
for (i = 0; i < size; i++) {
if (arr[i] <= 0) {
let temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// increment count of non-positive
// integers
j++;
}
}
return j;
}
/* Find the smallest positive missing
number in an array that contains
all positive integers */
function findMissingPositive(arr,size)
{
let i;
// Mark arr[i] as visited by making
// arr[arr[i] - 1] negative. Note that
// 1 is subtracted because index start
// from 0 and positive numbers start from 1
for (i = 0; i < size; i++) {
let x = Math.abs(arr[i]);
if (x - 1 < size && arr[x - 1] > 0)
arr[x - 1] = -arr[x - 1];
}
// Return the first index value at which
// is positive
for (i = 0; i < size; i++)
if (arr[i] > 0)
return i + 1; // 1 is added because indexes
// start from 0
return size + 1;
}
/* Find the smallest positive missing
number in an array that contains
both positive and negative integers */
function findMissing(arr,size)
{
// First separate positive and
// negative numbers
let shift = segregate(arr, size);
let arr2 = new Array(size - shift);
let j = 0;
for (let i = shift; i < size; i++) {
arr2[j] = arr[i];
j++;
}
// Shift the array and call
// findMissingPositive for
// positive part
return findMissingPositive(arr2, j);
}
// Driver code
let arr = [0, 10, 2, -10, -20];
let arr_size = arr.length;
let missing = findMissing(arr, arr_size);
document.write("The smallest positive missing number is " + missing);
// This code is contributed by rag2127
</script>
Producción
The smallest positive missing number is 1
Tenga en cuenta que este método modifica la array original. Podemos cambiar el signo de los elementos en la array segregada para recuperar el mismo conjunto de elementos. Pero aún perdemos el orden de los elementos. Si queremos mantener la array original como estaba, podemos crear una copia de la array y ejecutar este enfoque en la array temporal.
Otro enfoque: en este problema, hemos creado una lista llena de 0 con el tamaño del valor max() de nuestra array dada. Ahora, cada vez que encontramos un valor positivo en nuestra array original, cambiamos el valor de índice de nuestra lista a 1. Entonces, una vez que hayamos terminado, simplemente iteramos a través de nuestra lista modificada, el primer 0 que encontramos, su (valor de índice + 1) debería ser nuestra respuesta ya que el índice en python comienza desde 0.
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 first missing positive number from
// the given unsorted array
int firstMissingPos(int A[], int n)
{
// To mark the occurrence of elements
bool present[n + 1] = { false };
// Mark the occurrences
for (int i = 0; i < n; i++) {
// Only mark the required elements
// All non-positive elements and the elements
// greater n + 1 will never be the answer
// For example, the array will be {1, 2, 3} in the
// worst case and the result will be 4 which is n + 1
if (A[i] > 0 && A[i] <= n)
present[A[i]] = true;
}
// Find the first element which didn't appear in the
// original array
for (int i = 1; i <= n; i++)
if (!present[i])
return i;
// If the original array was of the type {1, 2, 3} in
// its sorted form
return n + 1;
}
// Driver code
int main()
{
int A[] = { 0, 10, 2, -10, -20 };
int size = sizeof(A) / sizeof(A[0]);
cout << firstMissingPos(A, size);
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C implementation of the approach
#include <stdbool.h>
#include <stdio.h>
// Function to return the first missing positive number from
// the given unsorted array
int firstMissingPos(int A[], int n)
{
// To mark the occurrence of elements
bool present[n + 1];
for (int i = 0; i < n; i++)
present[i] = false;
// Mark the occurrences
for (int i = 0; i < n; i++) {
// Only mark the required elements
// All non-positive elements and the elements
// greater n + 1 will never be the answer
// For example, the array will be {1, 2, 3} in the
// worst case and the result will be 4 which is n +
// 1
if (A[i] > 0 && A[i] <= n)
present[A[i]] = true;
}
// Find the first element which didn't appear in the
// original array
for (int i = 1; i <= n; i++)
if (!present[i])
return i;
// If the original array was of the type {1, 2, 3} in
// its sorted form
return n + 1;
}
// Driver code
int main()
{
int A[] = { 0, 10, 2, -10, -20 };
int size = sizeof(A) / sizeof(A[0]);
printf("%d", firstMissingPos(A, size));
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java Program to find the smallest positive missing number
import java.util.*;
public class GFG {
static int solution(int[] A)
{
int n = A.length;
// Let this 1e6 be the maximum element provided in
// the array;
int N = 1000010;
// To mark the occurrence of elements
boolean[] present = new boolean[N];
int maxele = Integer.MIN_VALUE;
// Mark the occurrences
for (int i = 0; i < n; i++) {
// Only mark the required elements
// All non-positive elements and the elements
// greater n + 1 will never be the answer
// For example, the array will be {1, 2, 3} in
// the worst case and the result will be 4 which
// is n + 1
if (A[i] > 0 && A[i] <= n)
present[A[i]] = true;
// find the maximum element so that if all the
// elements are in order can directly return the
// next number
maxele = Math.max(maxele, A[i]);
}
// Find the first element which didn't
// appear in the original array
for (int i = 1; i < N; i++)
if (!present[i])
return i;
// If the original array was of the
// type {1, 2, 3} in its sorted form
return maxele + 1;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 0, 10, 2, -10, -20 };
System.out.println(solution(A));
int arr[] = { -2, -1, 0, 1, 2, 3, 4 };
System.out.println(solution(arr));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 Program to find the smallest # positive missing number def solution(A): # Our original array m = max(A) # Storing maximum value if m < 1: # In case all values in our array are negative return 1 if len(A) == 1: # If it contains only one element return 2 if A[0] == 1 else 1 l = [0] * m for i in range(len(A)): if A[i] > 0: if l[A[i] - 1] != 1: # Changing the value status at the index of our list l[A[i] - 1] = 1 for i in range(len(l)): # Encountering first 0, i.e, the element with least value if l[i] == 0: return i + 1 # In case all values are filled between 1 and m return i + 2 # Driver Code A = [0, 10, 2, -10, -20] print(solution(A))
C#
// C# Program to find the smallest
// positive missing number
using System;
using System.Linq;
class GFG {
static int solution(int[] A)
{
// Our original array
int m = A.Max(); // Storing maximum value
// In case all values in our array are negative
if (m < 1) {
return 1;
}
if (A.Length == 1) {
// If it contains only one element
if (A[0] == 1) {
return 2;
}
else {
return 1;
}
}
int i = 0;
int[] l = new int[m];
for (i = 0; i < A.Length; i++) {
if (A[i] > 0) {
// Changing the value status at the index of
// our list
if (l[A[i] - 1] != 1) {
l[A[i] - 1] = 1;
}
}
}
// Encountering first 0, i.e, the element with least
// value
for (i = 0; i < l.Length; i++) {
if (l[i] == 0) {
return i + 1;
}
}
// In case all values are filled between 1 and m
return i + 2;
}
// Driver code
public static void Main()
{
int[] A = { 0, 10, 2, -10, -20 };
Console.WriteLine(solution(A));
}
}
// This code is contributed by PrinciRaj1992
PHP
<?php
// PHP Program to find the smallest
// positive missing number
function solution($A){//Our original array
$m = max($A); //Storing maximum value
if ($m < 1)
{
// In case all values in our array are negative
return 1;
}
if (sizeof($A) == 1)
{
//If it contains only one element
if ($A[0] == 1)
return 2 ;
else
return 1 ;
}
$l = array_fill(0, $m, NULL);
for($i = 0; $i < sizeof($A); $i++)
{
if( $A[$i] > 0)
{
if ($l[$A[$i] - 1] != 1)
{
//Changing the value status at the index of our list
$l[$A[$i] - 1] = 1;
}
}
}
for ($i = 0;$i < sizeof($l); $i++)
{
//Encountering first 0, i.e, the element with least value
if ($l[$i] == 0)
return $i+1;
}
//In case all values are filled between 1 and m
return $i+2;
}
// Driver Code
$A = array(0, 10, 2, -10, -20);
echo solution($A);
return 0;
?>
Javascript
<script>
// Javascript Program to find the smallest
// positive missing number
function solution(A)
{
let n = A.length;
// To mark the occurrence of elements
let present = new Array(n+1);
for(let i=0;i<n+1;i++)
{
present[i]=false;
}
// Mark the occurrences
for (let i = 0; i < n; i++)
{
// Only mark the required elements
// All non-positive elements and
// the elements greater n + 1 will never
// be the answer
// For example, the array will be {1, 2, 3}
// in the worst case and the result
// will be 4 which is n + 1
if (A[i] > 0 && A[i] <= n)
{
present[A[i]] = true;
}
}
// Find the first element which didn't
// appear in the original array
for (let i = 1; i <= n; i++)
{
if (!present[i])
{
return i;
}
}
// If the original array was of the
// type {1, 2, 3} in its sorted form
return n + 1;
}
// Driver Code
let A=[0, 10, 2, -10, -20]
document.write(solution(A));
</script>
Producción
1
Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesitan dos recorridos. Entonces la complejidad del tiempo es O(n). - Espacio Auxiliar: O(n).
el uso de la lista requerirá espacio adicional
Otro enfoque:
- El entero positivo más pequeño es 1. Primero verificaremos si 1 está presente en la array o no. Si no está presente, entonces 1 es la respuesta.
- Si está presente, vuelva a atravesar la array. La mayor respuesta posible es N+1 donde N es el tamaño de la array . Esto sucederá cuando la array tenga todos los elementos del 1 al N. Cuando atravesemos la array, si encontramos un número menor que 1 o mayor que N, lo cambiaremos a 1. Esto no cambiará nada, ya que la respuesta lo hará. siempre entre 1 y N+1. Ahora nuestra array tiene elementos del 1 al N.
- Ahora, para cada i-ésimo número, aumente arr[ (arr[i]-1) ] en N . Pero esto aumentará el valor más que N. Entonces, accederemos a la array mediante arr[(arr[i]-1)%N] . Lo que hemos hecho es que para cada valor hemos incrementado el valor en ese índice en N.
- Encontraremos ahora qué índice tiene un valor menor que N+1. Entonces i+1 será nuestra respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function for finding the first missing positive number
int firstMissingPositive(int arr[], int n)
{
int ptr = 0;
// Check if 1 is present in array or not
for (int i = 0; i < n; i++) {
if (arr[i] == 1) {
ptr = 1;
break;
}
}
// If 1 is not present
if (ptr == 0)
return 1;
// Changing values to 1
for (int i = 0; i < n; i++)
if (arr[i] <= 0 || arr[i] > n)
arr[i] = 1;
// Updating indices according to values
for (int i = 0; i < n; i++)
arr[(arr[i] - 1) % n] += n;
// Finding which index has value less than n
for (int i = 0; i < n; i++)
if (arr[i] <= n)
return i + 1;
// If array has values from 1 to n
return n + 1;
}
// Driver code
int main()
{
int arr[] = { 2, 3, -7, 6, 8, 1, -10, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
int ans = firstMissingPositive(arr, n);
cout << ans;
return 0;
}
C
// C program for the above approach
#include <stdio.h>
#include <stdlib.h>
// Function for finding the first
// missing positive number
int firstMissingPositive(int arr[], int n)
{
int ptr = 0;
// Check if 1 is present in array or not
for(int i = 0; i < n; i++)
{
if (arr[i] == 1)
{
ptr = 1;
break;
}
}
// If 1 is not present
if (ptr == 0)
return 1;
// Changing values to 1
for(int i = 0; i < n; i++)
if (arr[i] <= 0 || arr[i] > n)
arr[i] = 1;
// Updating indices according to values
for(int i = 0; i < n; i++)
arr[(arr[i] - 1) % n] += n;
// Finding which index has value less than n
for(int i = 0; i < n; i++)
if (arr[i] <= n)
return i + 1;
// If array has values from 1 to n
return n + 1;
}
// Driver code
int main()
{
int arr[] = { 2, 3, -7, 6, 8, 1, -10, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
int ans = firstMissingPositive(arr, n);
printf("%d", ans);
return 0;
}
// This code is contributed by shailjapriya
Java
// Java program for the above approach
import java.util.Arrays;
class GFG{
// Function for finding the first
// missing positive number
static int firstMissingPositive(int arr[], int n)
{
int ptr = 0;
// Check if 1 is present in array or not
for(int i = 0; i < n; i++)
{
if (arr[i] == 1)
{
ptr = 1;
break;
}
}
// If 1 is not present
if (ptr == 0)
return (1);
// Changing values to 1
for(int i = 0; i < n; i++)
if (arr[i] <= 0 || arr[i] > n)
arr[i] = 1;
// Updating indices according to values
for(int i = 0; i < n; i++)
arr[(arr[i] - 1) % n] += n;
// Finding which index has value less than n
for(int i = 0; i < n; i++)
if (arr[i] <= n)
return (i + 1);
// If array has values from 1 to n
return (n + 1);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 3, -7, 6, 8, 1, -10, 15 };
int n = arr.length;
int ans = firstMissingPositive(arr, n);
System.out.println(ans);
}
}
// This code is contributed by shailjapriya
Python3
# Python3 program for the above approach # Function for finding the first missing # positive number def firstMissingPositive(arr, n): ptr = 0 # Check if 1 is present in array or not for i in range(n): if arr[i] == 1: ptr = 1 break # If 1 is not present if ptr == 0: return(1) # Changing values to 1 for i in range(n): if arr[i] <= 0 or arr[i] > n: arr[i] = 1 # Updating indices according to values for i in range(n): arr[(arr[i] - 1) % n] += n # Finding which index has value less than n for i in range(n): if arr[i] <= n: return(i + 1) # If array has values from 1 to n return(n + 1) # Driver Code # Given array A = [ 2, 3, -7, 6, 8, 1, -10, 15 ] # Size of the array N = len(A) # Function call print(firstMissingPositive(A, N)) # This code is contributed by shailjapriya
C#
// C# program for the above approach
using System;
using System.Linq;
class GFG{
// Function for finding the first missing
// positive number
static int firstMissingPositive(int[] arr, int n)
{
int ptr = 0;
// Check if 1 is present in array or not
for(int i = 0; i < n; i++)
{
if (arr[i] == 1)
{
ptr = 1;
break;
}
}
// If 1 is not present
if (ptr == 0)
return 1;
// Changing values to 1
for(int i = 0; i < n; i++)
if (arr[i] <= 0 || arr[i] > n)
arr[i] = 1;
// Updating indices according to values
for(int i = 0; i < n; i++)
arr[(arr[i] - 1) % n] += n;
// Finding which index has value less than n
for(int i = 0; i < n; i++)
if (arr[i] <= n)
return i + 1;
// If array has values from 1 to n
return n + 1;
}
// Driver code
public static void Main()
{
int[] A = { 2, 3, -7, 6, 8, 1, -10, 15 };
int n = A.Length;
int ans = firstMissingPositive(A, n);
Console.WriteLine(ans);
}
}
// This code is contributed by shailjapriya
Javascript
<script>
// Javascript program for the above approach
// Function for finding the first
// missing positive number
function firstMissingPositive(arr, n)
{
let ptr = 0;
// Check if 1 is present in array or not
for(let i = 0; i < n; i++)
{
if (arr[i] == 1)
{
ptr = 1;
break;
}
}
// If 1 is not present
if (ptr == 0)
return 1;
// Changing values to 1
for(let i = 0; i < n; i++)
if (arr[i] <= 0 || arr[i] > n)
arr[i] = 1;
// Updating indices according to values
for(let i = 0; i < n; i++)
arr[(arr[i] - 1) % n] += n;
// Finding which index has value less than n
for(let i = 0; i < n; i++)
if (arr[i] <= n)
return i + 1;
// If array has values from 1 to n
return n + 1;
}
// Driver code
let arr = [ 2, 3, -7, 6, 8, 1, -10, 15 ];
let n = arr.length;
let ans = firstMissingPositive(arr, n);
document.write(ans);
// This code is contributed by telimayur
</script>
Producción:
4
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Otro enfoque:
- Recorra la array, ignore los elementos que son mayores que n y menores que 1.
- Mientras atraviesa, compruebe a[i]!=a[a[i]-1] si esta condición se cumple o no.
- Si la condición anterior es verdadera, intercambie a[i], a[a[i] – 1] && hasta que a[i] != a[a[i] – 1] la condición falle.
- Recorra la array y compruebe si a[i] != i + 1 y luego devuelva i + 1.
- Si todos son iguales a su índice, devuelve n+1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function for finding the first
// missing positive number
int firstMissingPositive(int arr[], int n)
{
// Loop to traverse the whole array
for (int i = 0; i < n; i++) {
// Loop to check boundary
// condition and for swapping
while (arr[i] >= 1 && arr[i] <= n
&& arr[i] != arr[arr[i] - 1]) {
swap(arr[i], arr[arr[i] - 1]);
}
}
// Checking any element which
// is not equal to i+1
for (int i = 0; i < n; i++) {
if (arr[i] != i + 1) {
return i + 1;
}
}
// Nothing is present return last index
return n + 1;
}
// Driver code
int main()
{
int arr[] = { 2, 3, -7, 6, 8, 1, -10, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
int ans = firstMissingPositive(arr, n);
cout << ans;
return 0;
}
// This code is contributed by Harsh kedia
Java
// Java program for the above approach
import java.util.Arrays;
class GFG{
// Function for finding the first
// missing positive number
static int firstMissingPositive(int arr[], int n)
{
// Check if 1 is present in array or not
for(int i = 0; i < n; i++)
{
// Loop to check boundary
// condition and for swapping
while (arr[i] >= 1 && arr[i] <= n
&& arr[i] != arr[arr[i] - 1]) {
int temp=arr[arr[i]-1];
arr[arr[i]-1]=arr[i];
arr[i]=temp;
}
}
// Finding which index has value less than n
for(int i = 0; i < n; i++)
if (arr[i] != i + 1)
return (i + 1);
// If array has values from 1 to n
return (n + 1);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {2, 3, -7, 6, 8, 1, -10, 15 };
int n = arr.length;
int ans = firstMissingPositive(arr, n);
System.out.println(ans);
}
}
// This code is contributed by mohit kumar 29.
Python3
# Python program for the above approach # Function for finding the first # missing positive number def firstMissingPositive(arr, n): # Loop to traverse the whole array for i in range(n): # Loop to check boundary # condition and for swapping while (arr[i] >= 1 and arr[i] <= n and arr[i] != arr[arr[i] - 1]): temp = arr[i] arr[i] = arr[arr[i] - 1] arr[temp - 1] = temp # Checking any element which # is not equal to i+1 for i in range(n): if (arr[i] != i + 1): return i + 1 # Nothing is present return last index return n + 1 # Driver code arr = [ 2, 3, -7, 6, 8, 1, -10, 15 ]; n = len(arr) ans = firstMissingPositive(arr, n) print(ans) # This code is contributed by shivanisinghss2110
C#
// C# program for the above approach
using System;
public class GFG{
// Function for finding the first
// missing positive number
static int firstMissingPositive(int[] arr, int n)
{
// Check if 1 is present in array or not
for(int i = 0; i < n; i++)
{
// Loop to check boundary
// condition and for swapping
while (arr[i] >= 1 && arr[i] <= n
&& arr[i] != arr[arr[i] - 1]) {
int temp = arr[arr[i] - 1];
arr[arr[i] - 1] = arr[i];
arr[i] = temp;
}
}
// Finding which index has value less than n
for(int i = 0; i < n; i++)
if (arr[i] != i + 1)
return (i + 1);
// If array has values from 1 to n
return (n + 1);
}
// Driver Code
static public void Main ()
{
int[] arr = {2, 3, -7, 6, 8, 1, -10, 15 };
int n = arr.Length;
int ans = firstMissingPositive(arr, n);
Console.WriteLine(ans);
}
}
// This code is contributed by ab2127
Javascript
<script>
// Javascript program for the above approach
// Function for finding the first
// missing positive number
function firstMissingPositive(arr,n)
{
// Check if 1 is present in array or not
for(let i = 0; i < n; i++)
{
// Loop to check boundary
// condition and for swapping
while (arr[i] >= 1 && arr[i] <= n
&& arr[i] != arr[arr[i] - 1]) {
let temp=arr[arr[i]-1];
arr[arr[i]-1]=arr[i];
arr[i]=temp;
}
}
// Finding which index has value less than n
for(let i = 0; i < n; i++)
if (arr[i] != i + 1)
return (i + 1);
// If array has values from 1 to n
return (n + 1);
}
// Driver Code
let arr=[2, 3, -7, 6, 8, 1, -10, 15 ];
let n = arr.length;
let ans = firstMissingPositive(arr, n);
document.write(ans);
// This code is contributed by patel2127
</script>
Producción
4
Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesitan dos recorridos. Entonces la complejidad del tiempo es O(n). - Espacio Auxiliar: O(1).
No se necesita espacio adicional, por lo que la complejidad del espacio es constante.
Otro enfoque simple con código pequeño y nítido.
Intuición: primero ordenaremos la array ahora, ya que tenemos que calcular el primer entero positivo faltante, y el entero positivo más pequeño es 1.
Por lo tanto, tome ans=1 e itere sobre la array una vez y compruebe si nums[i]==ans (significa que estamos comprobando el valor desde 1 hasta el número que falta).
Al iterar si esa condición cumple donde nums[i]==ans, luego incremente ans en 1 y nuevamente verifique la misma condición hasta el tamaño de la array.
Después de un escaneo de la array, obtuvimos el número faltante almacenado en la variable ans.
Ahora devuelva ese ans a la función como tipo de retorno en int.
La implementación del código de la intuición anterior es la siguiente:
C++
#include <bits/stdc++.h>
using namespace std;
int firstMissingPositive(vector<int>& nums) {
sort(nums.begin(),nums.end());
int ans=1;
for(int i=0;i<nums.size();i++)
{
if(nums[i]==ans)
ans++;
}
return ans;
}
int main() {
vector<int>arr={-1,0,8,1};
cout << firstMissingPositive(arr);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.Arrays;
class GFG {
public static int firstMissingPositive(int[] nums,
int n)
{
Arrays.sort(nums);
int ans = 1;
for (int i = 0; i < n; i++) {
if (nums[i] == ans)
ans++;
}
return ans;
}
public static void main(String[] args)
{
int arr[] = { 2, 3, -7, 6, 8, 1, -10, 15 };
int n = arr.length;
int ans = firstMissingPositive(arr, n);
System.out.println(ans);
}
}
Python3
# Python code for the same approach from functools import cmp_to_key def cmp(a, b): return (a - b) def firstMissingPositive(nums): nums.sort(key = cmp_to_key(cmp)) ans = 1 for i in range(len(nums)): if(nums[i] == ans): ans += 1 return ans # driver code arr = [-1, 0, 8, 1] print(firstMissingPositive(arr)) # This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
public class GFG {
static public int firstMissingPositive(int[] nums, int n)
{
Array.Sort(nums);
int ans = 1;
for (int i = 0; i < n; i++) {
if (nums[i] == ans)
ans++;
}
return ans;
}
// Driver Code
static public void Main()
{
int[] arr = { 2, 3, -7, 6, 8, 1, -10, 15 };
int n = arr.Length;
int ans = firstMissingPositive(arr, n);
Console.WriteLine(ans);
}
}
// This code is contributed by kothavvsaakash
Javascript
<script>
function firstMissingPositive(nums)
{
nums.sort((a,b)=>a-b);
let ans = 1;
for(let i = 0; i < nums.length; i++)
{
if(nums[i] == ans)
ans++;
}
return ans;
}
// driver code
let arr = [-1,0,8,1];
document.write(firstMissingPositive(arr));
// This code is contributed by shinjanpatra
</script>
Producción
2
Complejidad del tiempo: O(n*log(n))
Espacio Auxiliar: O(1)
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