Минимальное пропущенное число

142
10 декабря 2018, 21:50

Решаю на Java следующую задачу:

(Условие уточнили после моих вопросов, навеянных общением с пользователями). Необходимо найти минимальное натуральное число, которого нет во входном массиве.

На вход подается строка, содержащая целые числа в диапазоне от -10^9 до 10^9, разделенные пробелом. На выходе ожидается одно число, удовлетворяющее условию задачи.

Код немного переписал:

import java.util.*;
public class hh1 {
    public static void main(String[] args) {
        //int[] arr = {7, 3, 12, 5};
        //int[] arr = {6, 9, 5, 2, 3};
        int[] arr = {8, 6, 9, 81, -1000000001};
        if (arr==null) System.out.println("");
        else {
            List<Integer> list = new ArrayList<>();
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < arr.length; i++) {
                set.add(arr[i]);
            }
            for (Integer integer : set) {
                list.add(integer);
            }
            Collections.sort(list);

            for (int i = 0; i < list.size(); i++) {
                if (i + 1 >= list.size()) break;
                if (list.get(0) > 1 || list.get(0) < 0) {
                    System.out.println(1);
                    break;
                }
                if ((list.get(i + 1) - list.get(i)) > 1) {
                    int i1 = (list.get(i + 1) - list.get(i)) - 1;
                    System.out.println(list.get(i + 1) - i1);
                    break;
                } else {
                    System.out.println("");
                    break;
                }
            }
        }
    }
}

Пример:

Массив 6, 9, 5, 2, 3, 1 сортируем по возрастанию - 1, 2, 3, 5, 6, 9. Минимальный целый пропущенный элемент больше нуля это 4.

Исправил с учетом советов пользователей и отрицательных чисел(проходит на один тест больше, но 6 шт. из 29 не проходит, как тестируется мне не показывает). Возможно, я что-то не учел.

Как бы ее еще погонять?

Где ошибка?

Answer 1

С java знаком плохо, предложу такой псевдокод

Создать массив содержащий все элементы входного массива без дубликатов и превышающие 0, отсортированные по возрастанию.
//Насколько я понял, первая половина вашей программы делает примерно это
Если массив пуст, то
  Вывести 1
  Завершить.
Перебрать все элементы массива по очереди.
  Если значение элемента больше чем индекс + 1 то
    Вывести индекс + 1
    Завершить.
Если массив закончился, то вывести кол-во элементов + 1
Answer 2

Ошибка в том, что если во входном массиве будет отрицательное число X, то ваш алгоритм выдаст X+1.

int[] arr = {8, 6, 9, 81, -5};

Результат: -4. А должно быть 1.

Answer 3

import java.util.Scanner; import java.util.TreeSet;

public class min3 {

public static void main(String[] args) {
    TreeSet<Long> hs=new TreeSet <>();
    Scanner in = new Scanner(System.in);    
    boolean f= false;
    long count=1;
    try {
    while (in.hasNextLong()) {
        long a=in.nextLong();
            if(a>0) hs.add(a);
    } ;
    //int count=hs.iterator().next();

    for(Long e: hs) {
        if (count!=e) 
        {
            System.out.print(count);
            f=true;
            break;
        };
    count++;
    };
    }
    catch(Exception e) {};
    if(!f)System.out.print(count);
    //System.out.print(hs);
}

}

READ ALSO
Decompile .class file bytecode version 49.0(java 5)

Decompile .class file bytecode version 49.0(java 5)

Столкнулся с такой проблемой

177
Синхронизировать ключи строк в android и ios

Синхронизировать ключи строк в android и ios

Необходимо создать один файл с ключами (очевидно чтобы удешевить работу переводчиков) У нас два проекта: android и iosПереводы хранятся в POEditor,...

131
Форматирование LocalDateTime перед сохранением в базу в Spring Boot приложением

Форматирование LocalDateTime перед сохранением в базу в Spring Boot приложением

Сохраняю в базу дату и время события, для этого в классе использую LocalDateTime, в базе это выглядит вот так 2018-09-05 10:42:58616000, есть ли способ, как-то...

120
Вылетает приложение при поиске AutoCompleteTextView

Вылетает приложение при поиске AutoCompleteTextView

В активити расположен AutoCompleteTextView, вот собственно код:

173