Рубрики

Найти наименьшее положительное число, отсутствующее в несортированном массиве | Комплект 1

Вам дан несортированный массив с положительными и отрицательными элементами. Вы должны найти наименьшее положительное число, отсутствующее в массиве за время O (n), используя постоянное дополнительное пространство. Вы можете изменить исходный массив.

Примеры

 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 

Наивным методом решения этой проблемы является поиск всех натуральных чисел, начиная с 1 в данном массиве. Возможно, нам придется искать не более n + 1 чисел в данном массиве. Таким образом, это решение принимает O (n ^ 2) в худшем случае.

Мы можем использовать сортировку, чтобы решить ее в меньшей сложности. Мы можем отсортировать массив за O (nLogn) время. Как только массив отсортирован, все, что нам нужно сделать, — это линейное сканирование массива. Таким образом, этот подход занимает O (nLogn + n) время, которое равно O (nLogn).

Мы также можем использовать хеширование . Мы можем построить хеш-таблицу всех положительных элементов в данном массиве. После того, как хэш-таблица построена. Мы можем посмотреть в хеш-таблице все положительные целые числа, начиная с 1. Как только мы находим число, которого нет в хеш-таблице, мы возвращаем его. Этот подход может занять в среднем O (n) времени, но требует O (n) дополнительного пространства.

AO (n) время и O (1) дополнительное пространство решение:
Идея похожа на этот пост. Мы используем элементы массива в качестве индекса. Чтобы отметить наличие элемента x, мы меняем значение в индексе x на отрицательное . Но этот подход не работает, если есть неположительные (-ve и 0) числа. Таким образом, мы отделяем положительные числа от отрицательных в качестве первого шага, а затем применяем подход.

Ниже приведен двухшаговый алгоритм.
1) Отделите положительные числа от других, т. Е. Переместите все неположительные числа в левую сторону. В следующем коде функция segregate () выполняет эту часть.
2) Теперь мы можем игнорировать неположительные элементы и рассматривать только ту часть массива, которая содержит все положительные элементы. Обходим массив, содержащий все положительные числа и, чтобы отметить наличие элемента x, мы меняем знак значения в индексе x на отрицательный. Мы снова обходим массив и печатаем первый индекс, который имеет положительное значение . В следующем коде функция findMissingPositive () выполняет эту часть. Обратите внимание, что в findMissingPositive мы вычли 1 из значений, так как индексы начинаются с 0 в C.

C ++

/ * C ++ программа для поиска наименьшего положительного пропущенного числа * /
#include <bits/stdc++.h>

using namespace std;

  
/ * Утилита для обмена на целые числа * /

void swap(int* a, int* b)

{

    int temp;

    temp = *a;

    *a = *b;

    *b = temp;

}

  
/ * Сервисная функция, которая помещает все
неположительные (0 и отрицательные) числа слева
сторона arr [] и возвращаемое количество таких чисел * /

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++; // увеличиваем количество неположительных чисел

        }

    }

  

    return j;

}

  
/ * Найти наименьшее положительное пропущенное число
в массиве, который содержит все натуральные числа * /

int findMissingPositive(int arr[], int size)

{

    int i;

  

    // Пометить arr [i] как посещенное, сделав arr [arr [i] - 1] отрицательным.

    // Обратите внимание, что 1 вычитается, потому что начало индекса

    // с 0 и положительные числа начинаются с 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];

    }

  

    // Возвращаем первое значение индекса, при котором положительно

    for (i = 0; i < size; i++)

        if (arr[i] > 0)

            // 1 добавлено, потому что индексы начинаются с 0

            return i + 1;

  

    return size + 1;

}

  
/ * Найти наименьший недостающий позитив
число в массиве, который содержит
как положительные, так и отрицательные целые числа * /

int findMissing(int arr[], int size)

{

    // Первые отдельные положительные и отрицательные числа

    int shift = segregate(arr, size);

  

    // Смещаем массив и вызываем findMissingPositive for

    // положительная часть

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

    cout << "The smallest positive missing number is " << missing;

    return 0;

}

  
// Это код, предоставленный rathbhupendra

С

/ * C программа для поиска наименьшего положительного пропущенного числа * /
#include <stdio.h>
#include <stdlib.h>

  
/ * Утилита для обмена на целые числа * /

void swap(int* a, int* b)

{

    int temp;

    temp = *a;

    *a = *b;

    *b = temp;

}

  
/ * Сервисная функция, которая помещает все
неположительные (0 и отрицательные) числа слева
сторона arr [] и возвращаемое количество таких чисел * /

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++; // увеличиваем количество неположительных чисел

        }

    }

  

    return j;

}

  
/ * Найти наименьшее положительное пропущенное число
в массиве, который содержит все натуральные числа * /

int findMissingPositive(int arr[], int size)

{

    int i;

  

    // Пометить arr [i] как посещенное, сделав arr [arr [i] - 1] отрицательным.

    // Обратите внимание, что 1 вычитается, потому что начало индекса

    // с 0 и положительные числа начинаются с 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];

    }

  

    // Возвращаем первое значение индекса, при котором положительно

    for (i = 0; i < size; i++)

        if (arr[i] > 0)

            // 1 добавлено, потому что индексы начинаются с 0

            return i + 1;

  

    return size + 1;

}

  
/ * Найти наименьший недостающий позитив
число в массиве, который содержит
как положительные, так и отрицательные целые числа * /

int findMissing(int arr[], int size)

{

    // Первые отдельные положительные и отрицательные числа

    int shift = segregate(arr, size);

  

    // Смещаем массив и вызываем findMissingPositive for

    // положительная часть

    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-программа для поиска самых маленьких
// положительное пропущенное число

import java.util.*;

  

class Main {

  

    / * Служебная функция, которая ставит все неположительные

       (0 и отрицательные) числа на левой стороне

       arr [] и возвращаемое количество таких чисел * /

    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;

                // увеличение числа неположительных значений

                // целые числа

                j++;

            }

        }

  

        return j;

    }

  

    / * Найти наименьший недостающий позитив

       число в массиве, который содержит

       все натуральные числа * /

    static int findMissingPositive(int arr[], int size)

    {

        int i;

  

        // Пометить arr [i] как посещенный, сделав

        // arr [arr [i] - 1] минус. Обратите внимание, что

        // 1 вычитается, потому что начало индекса

        // с 0 и положительные числа начинаются с 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];

        }

  

        // Возвращаем первое значение индекса, при котором

        // положительно

        for (i = 0; i < size; i++)

            if (arr[i] > 0)

                return i + 1; // добавлено 1, потому что индексы

        // начинаем с 0

  

        return size + 1;

    }

  

    / * Найти наименьший недостающий позитив

       число в массиве, который содержит

       как положительные, так и отрицательные целые числа * /

    static int findMissing(int arr[], int size)

    {

        // Первый отдельный позитив и

        // отрицательные числа

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

        }

        // Сдвиг массива и вызов

        // findMissingPositive for

        // положительная часть

        return findMissingPositive(arr2, j);

    }

    // основная функция

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

    }

}

C #

// C # программа для поиска самых маленьких
// положительное пропущенное число

using System;

  

class main {

  

    // Сервисная функция, которая помещает все

    // не положительный (0 и отрицательный)

    // числа на левой стороне arr []

    // и возвращаем количество таких чисел

    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;

  

                // увеличение числа неположительных значений

                // целые числа

                j++;

            }

        }

  

        return j;

    }

  

    // Находим наименьшее недостающее положительное

    // номер в массиве, который содержит

    // все натуральные числа

    static int findMissingPositive(int[] arr, int size)

    {

        int i;

  

        // Пометить arr [i] как посещенный, сделав

        // arr [arr [i] - 1] минус. Обратите внимание, что

        // 1 вычитается как начало индекса из

        // 0 и положительные числа начинаются с 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];

        }

  

        // Возвращаем первое значение индекса в

        // что положительно

        for (i = 0; i < size; i++)

            if (arr[i] > 0)

                return i + 1;

  

        // добавлено 1, потому что индексы

        // начинаем с 0

        return size + 1;

    }

  

    // Находим наименьший положительный

    // отсутствует номер в массиве

    // содержит как положительный, так и

    // отрицательные целые числа

    static int findMissing(int[] arr, int size)

    {

  

        // Первый отдельный позитив и

        // отрицательные числа

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

        }

  

        // Сдвиг массива и вызов

        // findMissingPositive for

        // положительная часть

        return findMissingPositive(arr2, j);

    }

  

    // основная функция

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

    }

}

  
// Этот код предоставлен Anant Agarwal.


Выход:

The smallest positive missing number is 1 

Обратите внимание, что этот метод изменяет исходный массив. Мы можем изменить знак элементов в выделенном массиве, чтобы вернуть тот же набор элементов. Но мы все еще теряем порядок элементов. Если мы хотим сохранить исходный массив таким, какой он был, то мы можем создать копию массива и запустить этот подход для временного массива.

Другой подход: в этой задаче мы создали список, полный 0 с размером значения max () нашего данного массива. Теперь, когда мы сталкиваемся с любым положительным значением в нашем исходном массиве, мы меняем значение индекса нашего списка на 1. Итак, после того, как мы закончим, мы просто перебираем наш измененный список, первый 0, с которым мы сталкиваемся, его (значение индекса + 1) должен быть наш ответ, так как индекс в Python начинается с 0.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата первого пропущенного положительного
// номер из данного несортированного массива

int firstMissingPos(int A[], int n)

{

  

    // Чтобы отметить вхождение элементов

    bool present[n + 1] = { false };

  

    // Пометить вхождения

    for (int i = 0; i < n; i++) {

  

        // Отметим только необходимые элементы

        // Все неположительные элементы и

        // элементы больше n + 1 никогда не будут

        // будь ответом

        // Например, массив будет {1, 2, 3}

        // в худшем случае и результат

        // будет 4, что равно n + 1

        if (A[i] > 0 && A[i] <= n)

            present[A[i]] = true;

    }

  

    // Найти первый элемент, который не

    // появляются в исходном массиве

    for (int i = 1; i <= n; i++)

        if (!present[i])

            return i;

  

    // Если исходный массив был

    // набираем {1, 2, 3} в отсортированном виде

    return n + 1;

}

  
// Код драйвера

int main()

{

  

    int A[] = { 0, 10, 2, -10, -20 };

    int size = sizeof(A) / sizeof(A[0]);

    cout << firstMissingPos(A, size);

}

  
// Этот код предоставлен gp6

Джава

// Java-программа для поиска самых маленьких
// положительное пропущенное число

import java.util.Arrays;

public class GFG {

  

    static int solution(int[] A)

    { // Наш оригинальный массив

  

        int m = Arrays.stream(A).max().getAsInt(); // Сохранение максимального значения

        if (m < 1) // Если все значения в нашем массиве отрицательны

        {

            return 1;

        }

        if (A.length == 1) {

  

            // Если он содержит только один элемент

            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) {

                if (l[A[i] - 1] != 1) // Изменение значения значения по индексу нашего списка

                {

                    l[A[i] - 1] = 1;

                }

            }

        }

        for (i = 0; i < l.length; i++) // Обнаружение первого 0, т.е. элемента с наименьшим значением

        {

            if (l[i] == 0) {

                return i + 1;

            }

        }

        // Если все значения заполнены от 1 до m

        return i + 2;

    }

  

    public static void main(String[] args)

    {

  

        int A[] = { 0, 10, 2, -10, -20 };

        System.out.println(solution(A));

    }

}
// Этот код предоставлен 29AjayKumar

Python 3

# Программа Python для поиска самых маленьких
# положительное пропущенное число

  

def solution(A):# Наш оригинальный массив

  

    m = max(A) # Сохранение максимального значения

    if m < 1:

          

        # Если все значения в нашем массиве отрицательны

        return 1 

    if len(A) == 1:

          

        # Если он содержит только один элемент

        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:

                  

                # Изменение значения статуса по индексу нашего списка

                l[A[i] - 1] = 1 

    for i in range(len(l)):

          

        # Обнаружение первого 0, т. Е. Элемента с наименьшим значением

        if l[i] == 0

            return i + 1

            # Если все значения заполнены от 1 до m

    return i + 2     

  

A = [0, 10, 2, -10, -20]

print(solution(A))

C #

// C # Программа для поиска самых маленьких
// положительное пропущенное число

using System;

using System.Linq;

  

class GFG {

    static int solution(int[] A)

    {

        // Наш оригинальный массив

  

        int m = A.Max(); // Сохранение максимального значения

  

        // Если все значения в нашем массиве отрицательны

        if (m < 1) {

            return 1;

        }

        if (A.Length == 1) {

  

            // Если он содержит только один элемент

            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) {

                // Изменение значения значения по индексу нашего списка

                if (l[A[i] - 1] != 1) {

                    l[A[i] - 1] = 1;

                }

            }

        }

  

        // Обнаружение первого 0, т.е. элемента с наименьшим значением

        for (i = 0; i < l.Length; i++) {

            if (l[i] == 0) {

                return i + 1;

            }

        }

  

        // Если все значения заполнены от 1 до m

        return i + 2;

    }

  

    // Код драйвера

    public static void Main()

    {

        int[] A = { 0, 10, 2, -10, -20 };

        Console.WriteLine(solution(A));

    }

}

  
// Этот код предоставлен PrinciRaj1992

PHP

<?php 
// PHP программа для поиска самых маленьких
// положительное пропущенное число

   

function solution($A){// Наш оригинальный массив

   

    $m = max($A); // Сохранение максимального значения

    if ($m < 1)

    {         

        // Если все значения в нашем массиве отрицательны

        return 1;

    }

    if (sizeof($A) == 1)

    {  

        // Если он содержит только один элемент

        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)

            {

                  

                // Изменение значения значения по индексу нашего списка

                $l[$A[$i] - 1] = 1;

            }

        }

    }

    for ($i = 0;$i < sizeof($l); $i++)

    {

           

        // Обнаружение первого 0, т.е. элемента с наименьшим значением

        if ($l[$i] == 0) 

            return $i+1;

    }

            // Если все значения заполнены от 1 до m

    return $i+2;    

}

  

$A = array(0, 10, 2, -10, -20);

echo solution($A);

return 0;

?>

Выход:

 1 

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти наименьшее положительное число, отсутствующее в несортированном массиве | Комплект 1

0.00 (0%) 0 votes