2

Найти минимальное натуральное число (положительное, целое, большее 0), которого нет в исходном массиве A.

Например:

Для A = [1, 3] ответ: 2

Для A = [1, 4, 6, 1, 3, 2] ответ: 5

8
  • Отсортируй массив и в один проход найди ответ.
    – Akina
    13 апр 2018 в 5:26
  • Я так делаю, но что-то пока не получается. Вы не могли бы подсказать как сделать?
    – Cool_Dude
    13 апр 2018 в 5:43
  • Что не получается- отсортировать?
    – MBo
    13 апр 2018 в 5:51
  • Взаимоисключающие параграфы: "найти в этом массиве число, которого нет в этом массиве"? Поправьте условие.
    – slippyk
    13 апр 2018 в 5:57
  • Условие так и есть т.е. найти в массиве минимальное число, которое нет в массиве. Например А {1, 3} - Ответ: 2.
    – Cool_Dude
    13 апр 2018 в 6:00

6 ответов 6

2

На C++ не писатель, но могу предложить два варианта:

Исходные данные:

int a[ 6 ] = { 1, 4, 6, 1, 3, 2 };
int size = sizeof( a ) / sizeof( a[ 0 ] );

Вариант 1:

т.к. по условию число должно быть больше 0, то начиная с 1 проверяем все числа, которые не входят в массив. Первое и будет тем самым.

int min = 1;

while (true)
{
    bool isContain = false;

    for (int i = 0; i < size; i++)
    {
        if (min == a[ i ])
        {
            isContain = true;
            break;
        }
    }

    if (isContain)
    {
        min++;
    }
    else
    {
        std::cout << min << "\n";
        break;
    }
}

Вариант 2:

Сначала сортируем исходный массив (по возрастанию в данном случае), и проверяем разность соседних элементов. Если получаем:

  • 0 - элементы равны;
  • 1 - элементы идут по порядку;
  • 2 и более - значит в этом диапазоне и находится минимальный элемент.

Прибавляем 1 к элементу, который находится левее в паре - это значение и будет минимальным.

for (int j = 1; j < size; j++)
{
    for (int i = 0; i < size - j; i++)
    {
        if (a[ i ] > a[ i + 1 ])
        {
            int b = a[ i ];
            a[ i ] = a[ i + 1 ];
            a[ i + 1 ] = b;
        }
    }
}

for (int i = 1; i < size; i++)
{
    if (a[ i ] - a[ i - 1 ] > 1)
    {
        std::cout << a[ i - 1 ] + 1 << "\n";
        break;
    }
}
1
  • Не ясно зачем квадратичный алгоритм для сортировки использовать. Как есть второй вариант не работает. Для a[] = {-1}; ожидалось: 1 вывод, а ничего не выводит
    – jfs
    13 апр 2018 в 15:46
1

берите число n = 1 ; Ищите в массиве это число. Если оно есть, то ++n; и повторяем по циклу, пока не будет в массиве такого числа.

Или сортируйте массив, и допустим он имеет размер 10:

const int sz = 10;
int m[10];
// инициализация, потом сортировка 
int k = 1;    
for (int i = 0; i < sz; ++i) {
    if ( m[i] == k )  {
        if (m[i] == m[i +1]) continue;            
          ++k;            
    }
    else  {         
        cout << "это число:  " << k;            
        break;
    }
}
3
  • решение не работает для int m[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1};. Ожидаемый вывод: 2. Ваш код выводит: это число: 1.
    – jfs
    13 апр 2018 в 15:05
  • Я и не говорил, что я написал красивый код, где учтены все обстоятельства. Я этого делать и не должен, поскольку я просто предлогаю вариант и не тестирую и сопроваждаю, а потом сдаю код на проверку, не пишу за кого то код. 13 апр 2018 в 15:18
  • 1
    решение неверное. Причём здесь красота. Ответ просто неправильный
    – jfs
    13 апр 2018 в 15:43
1

Линейный алгоритм:

  1. отметить все числа в интервале [1, n], которые есть во входном массиве, где n это размер массива
  2. найти первое неотмеченное число.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main()
{
  // read numbers
  std::istream_iterator<int> numbers {std::cin}, eof;
  std::vector<int> arr(numbers, eof);

  // mark numbers in [1, n] range that are in the array
  size_t n = arr.size();
  std::vector<bool> m(n+1, false);
  for (int x : arr)
    if (1 <= x && x <= n)
      m[x-1] = true;

  // find the first absent number (position + 1)
  auto it = std::find(std::begin(m), std::end(m), false);
  std::cout << (std::distance(std::begin(m), it) + 1) << std::endl;
}

Пример.

3
  • вектора и другие контейнера не обсуждались, вопрос касался массивам 13 апр 2018 в 19:12
  • 1
    не нужно придумывать. В вопросе нет никаких ограничений на использование вектора. В примере ввод читается со стандартного ввода, из статического массива ещё проще было бы взять ввод¶ То что я вам на ошибку в вашем решении указал, что оно не работает, ещё не значит, что на другие правильные рабочие ответы (на ссылку в ответе нажмите) нужно минусы ставить. Я смотрю ещё кто-те не поленился минус ответу двухлетней давности поставить. Мелкий пакостник однако попался.
    – jfs
    13 апр 2018 в 19:45
  • я хотел сказать шагов, а не памяти 13 апр 2018 в 19:54
0

Моё компактное и красивое решение без лишних сортировок

int mas[] = {1, -1, 7, 0, 1, 2, 4};
int length = sizeof(mas) / sizeof(mas[0]);
int res = 1;
for (int j = 0; j < length; j++)
    for (int i = 0; i < length; i++) {
        if (mas[i] == res) {
            res++;
            break;
        }
    }
cout<<res;
13
  • Спасибо за ответ. Ну вот я так и не понял, первый цикл, зачем он нужен?
    – Cool_Dude
    13 апр 2018 в 8:18
  • неправильно будет работать ваше компактгое и красивое решение 13 апр 2018 в 8:34
  • 1
    Компактное, красивое, медленное решение, зато без лишних сортировок!
    – int3
    13 апр 2018 в 8:35
  • 2
    @ARHovsepyan кто комментарий удалил не знаю. Грубости там не помню, только факты: вы бездоказательно (без оснований назвали ответ неправильным), имея при этом свой сломанный ответ к тому же вопросу (результат что правильный ответ с минусом, а неправильный в плюсе—это вредительство). Я это считаю подлостью. Если этот комментарий кто-то удалит. Пишите¶ Не нужно пробел после \@ ставить, что за детский сад.
    – jfs
    13 апр 2018 в 19:55
  • 1
    Комментарий был и был удалён. Судя по всему он был автоматически удалён системой после проставления на нём флага из-за совпадения какого-то слова из него со списком из "плохих" слов, которые Николас добавлял в какой-то там скрипт автоматического удаления.
    – ЮрийСПб
    15 апр 2018 в 16:11
0

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

0

Задача имеет классическое решение за линейное время (быстрее чем сортировка) и без дополнительной памяти (не нужны дополнительные массивы флагов и т.п.). С другой стороны содержимое массива меняется, в каком-то смысле это сортировка специального вида.

Идём по массиву и если видим элемент, который можно поместить на своё место, делаем это. В конце прохода все элементы для которых это возможно стоят на своих местах (v[i] == i + 1). Если в каком-то месте равенство нарушено, числа i + 1 в массиве нет.

#include <iostream>
#include <iterator>
#include <utility>
#include <vector>

int absent_number(std::vector<int> &v) {
    const int n = v.size();
    for (int i = 0; i < n; ++i) {
        while (1 <= v[i] && v[i] <= n && v[v[i] - 1] != v[i]) {
            std::swap(v[i], v[v[i] - 1]);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (v[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

void test(std::vector<int> v) {
    std::cout << '\n';
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n' << absent_number(v) << '\n';
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

int main()
{
    test({1, 3});
    test({1, 4, 6, 1, 3, 2});
    test({1, 4, 6, 5, 3, 2});
}
$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror -O3 absent-number.cpp && ./a.out 

1 3 
2
1 3 

1 4 6 1 3 2 
5
1 2 3 4 1 6 

1 4 6 5 3 2 
7
1 2 3 4 5 6

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.