查找未排序数组中缺失的最小正数|S1

2021年5月1日17:18:46 发表评论 914 次浏览

本文概述

``````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``````

O(n)时间和O(1)额外空间解决方案：

。但是, 如果存在非正数(-ve和0), 则此方法无效。因此, 我们首先将正数与负数分开, 然后应用该方法。

1)将正数与其他数字分开, 即, 将所有非正数移到左侧。在下面的代码中, segregate()函数完成了这一部分。

2)现在我们可以忽略非正元素, 而只考虑包含所有正元素的数组部分。我们遍历包含所有正数的数组, 并标记元素x的存在, 我们将索引x处的值符号更改为负数。我们再次遍历数组,

。在下面的代码中, findMissingPositive()函数完成了这一部分。请注意, 在findMissingPositive中, 我们从值中减去了1, 因为C中的索引从0开始。

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]);
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);
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);
}

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 becuase 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);
}
//main function
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);
}
}``````

python

``````''' Python 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;

//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);
}

//main function
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.``````

``The smallest positive missing number is 1``

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
//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 gp6``````

Java

``````//Java Program to find the smallest
//positive missing number
import java.util.Arrays;
public class GFG {

static int solution( int [] A)
{
int n = A.length;

//To mark the occurrence of elements
boolean [] present = new boolean [n + 1 ];

//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
//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 ;
}

public static void main(String[] args)
{

int A[] = { 0 , 10 , 2 , - 10 , - 20 };
System.out.println(solution(A));
}
}
//This code is contributed by 29AjayKumar``````

Python 3

``````# Python 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

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;
}

\$A = array (0, 10, 2, -10, -20);
echo solution( \$A );
return 0;
?>``````

``1``