Как найти пропущенное число с диапазоном миллионов чисел в массиве, где присутствуют дубликаты?

Я задаю этот вопрос в связи с этим вопросом, опубликованным несколько месяцев назад.

В настоящее время в приложении, над которым я работаю, я получаю серию чисел, где числа могут отсутствовать и дублироваться, но упорядочены по возрастанию.

Было две проблемы.

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

  2. Но если есть дубликаты, этот подход больше не работает.

Как я могу решить проблему? Никакая логика, кажется, не работает. И даже если бы это было (используя цикл), это было бы неэффективно.

ПРИМЕЧАНИЕ. Я также искал некоторые библиотеки, но не смог их найти.

Кажется, вы могли бы просто начать с удаления дубликатов, а затем применить предыдущий алгоритм. Поскольку числа упорядочены, удаление дубликатов имеет эффективность алгоритмов O (n).

Alexandre Fenyo 20.02.2023 09:56

Как мне это сделать? без петель? Данные моего приложения должны обновляться каждые 2-3 секунды, поэтому такой подход не очень хорош, не так ли?

Sambhav Khandelwal 20.02.2023 09:57

Извините, но я что-то упустил. Дубликаты необходимы для правильной работы приложения и не могут быть устранены.

Sambhav Khandelwal 20.02.2023 09:59

Вы не должны удалять дубликаты из фактической полезной нагрузки. Вы должны удалить дубликаты из временной копии этих данных, чтобы алгоритм работал.

QBrute 20.02.2023 10:04

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

Tim Moore 20.02.2023 10:33

Это действительно зависит от вашего конкретного варианта использования. Если несколько тысяч чисел отсутствуют, вы можете хранить диапазоны вместо каждого числа по отдельности.

MC Emperor 20.02.2023 11:01

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

vsfDawg 20.02.2023 13:30
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
0
8
102
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

Насколько я знаю, нет никакого способа обнаружить пропущенное число в списке, кроме перебора.

Если ваш массив отсортирован, он должен выглядеть примерно так:

[1,2,3,3,4,6]

Итак, этот код должен выполнять работу:

int getMissingNumber(int[] numbers){
    for (int i=0; i<numbers.length -1; i++){
        int current = numbers[i];
        int next = numbers[i+1];
        if (next - current > 1){
            return current + 1;
        }
    }
    return -1;
}

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

Loop хорош для небольших диапазонов. Но у меня есть миллионы чисел в моем массиве. это не эффективно

Sambhav Khandelwal 20.02.2023 14:05

Я просто попытался посмотреть, насколько я могу разбить задачи, используя Fork Join в качестве забавного упражнения, чтобы лучше узнать библиотеку (также потому, что я думал, что разделение задачи на более мелкие задачи и их параллельная обработка займет меньше времени) и сравнил его с простым циклом for.

public class misc {
    public void getMissingNumbers(int[] numbers){
        for (int i=0; i<numbers.length -1; i++){
            int current = numbers[i];
            int next = numbers[i+1];
            if (current+1 != next){
                System.out.println("Problem! - "+current+" "+next);
            }
        }
    }
     
     public static void main(String []args){
         int[] range = IntStream.rangeClosed(1, 50_000_000).toArray();
         int index = 50000;
         range[index] =  range[index-1];  //duplicate
         index = 390;
         range[index] =  range[index-1];
         index = 500390;
         range[index] =  range[index-1];
         index = 2500390;
         range[index] =  range[index-1];
         
         ZonedDateTime now = ZonedDateTime.now();
         misc m = new misc();
         m.getMissingNumbers(range);
         System.out.printf("%s exec time: %dms\n",
                 m.getClass().getSimpleName(),
                 ChronoUnit.MILLIS.between(now, ZonedDateTime.now()));
         
         now = ZonedDateTime.now();
         ForkJoinPool forkJoinPool = ForkJoinPool.commonPool();
         breakDownRecursively bdr = new breakDownRecursively(range);
         forkJoinPool.invoke(bdr);
         System.out.printf("%s exec time: %dms\n",
                 bdr.getClass().getSimpleName(),
                 ChronoUnit.MILLIS.between(now, ZonedDateTime.now()));
     }
}

class breakDownRecursively extends RecursiveAction {
    private final int[] arr;
    private final ArrayList<Integer> arrlst = new ArrayList<>();
    
    public breakDownRecursively(int[] arr) {
        this.arr = arr;
    }
    
    public void compute() {
        int n = arr.length;
        if (arr.length < 2) return;
        int mid = arr.length / 2;

        int[] left = new int[mid];
        System.arraycopy(arr, 0, left, 0, mid);

        int[] right = new int[arr.length - mid];
        System.arraycopy(arr, mid, right, 0, arr.length - mid);

        invokeAll(new breakDownRecursively(left), new breakDownRecursively(right));
        compare(left, right);
    }
    
    private void compare(int[] left, int[] right) {
        if (left.length == 1 && right.length == 1) {
            if (left[0]+1 != right[0]) {
                //System.out.println("Problem! - "+left[0]+" "+right[0]);
            }
        }
    }
}

Выход:

Problem! - 390 390
Problem! - 390 392
Problem! - 50000 50000
Problem! - 50000 50002
Problem! - 500390 500390
Problem! - 500390 500392
Problem! - 2500390 2500390
Problem! - 2500390 2500392
misc exec time: 60ms
Problem! - 390 392
Problem! - 500390 500392
Problem! - 2500390 2500392
breakDownRecursively exec time: 2435ms

Я полагаю, что, вероятно, где-то допустил ошибку во время реализации fork join, но, по крайней мере, вы должны увидеть, что цикл for не НАСТОЛЬКО плох.

и когда я использовал Runnable:

     int mid = range.length/2;
     int[] half1 = new int[mid+1];
     System.arraycopy(range, 0, half1, 0, mid+1);
     int[] half2 = new int[mid];
     System.arraycopy(range, mid, half2, 0, range.length - mid);
     RunnableTask r1 = new RunnableTask(half1);
     RunnableTask r2 = new RunnableTask(half2);
     now = ZonedDateTime.now();
     Thread t1 = new Thread(r1);
     Thread t2 = new Thread(r2);
     
     t1.start();
     t2.start();
     t1.join();
     t2.join();
     
     System.out.printf("%s exec time: %dms\n",
             r1.getClass().getSimpleName(),
             ChronoUnit.MILLIS.between(now, ZonedDateTime.now()));

class RunnableTask implements Runnable{
    private final int[] arr;
    public RunnableTask(int[] arr) {
        this.arr = arr;
    }
    @Override
    public void run() {
        // TODO Auto-generated method stub
        for (int i=0; i<arr.length -1; i++){
            int current = arr[i];
            int next = arr[i+1];
            if (current+1 != next){
                System.out.println("Problem! - "+current+" "+next);
            }
        }
    }
    
}

Выход:

Problem! - 390 390
Problem! - 390 392
Problem! - 50000 50000
Problem! - 50000 50002
Problem! - 500390 500390
Problem! - 500390 500392
Problem! - 2500390 2500390
Problem! - 2500390 2500392
RunnableTask exec time: 49ms

Только немного лучше, чем цикл for.

Спасибо за ответ @experimentunit1998X. Я не смог понять второй подход, который вы использовали. Кроме того, я не мог понять вывод. Например, Problem! - 390 390, первое выражение в выводе, почему оба числа одинаковы?

Sambhav Khandelwal 20.02.2023 16:58

Вы читали код? Они создали массив из 50 мл элементов в верхней части файла main. System.out.println("Problem! - "+current+" "+next); Вы видите, что текущий элемент массива (390) равен следующему элементу массива (390). Или текущий элемент массива (390) не равен на 1 меньше, чем следующий элемент массива (392). поэтому пропущено число (391). Смысл этого кода в том, чтобы показать, что цикл завершился за 60 мс, а Runnable завершился за 49 мс. Вы, кажется, считаете, что петля - это плохо. Они доказывают, что это не так.

tbatch 20.02.2023 17:57

Я, вероятно, запутался со вторым подходом, но то, что я действительно хотел сделать, это что-то вроде использования runnable, разбить его на списки определенной длины и обработать каждый. Проблема со вторым подходом, который я не смог решить, заключается в том, что в конце дня он снова «объединит» разбитые части и обработает уже обработанные элементы массива.

experiment unit 1998X 21.02.2023 02:07

проблема в том, что текущий элемент и следующий дублируются, и на следующей итерации текущий элемент не на 1 меньше, чем следующий элемент, поэтому две ошибки приходят одна за другой

experiment unit 1998X 21.02.2023 02:08

Я получаю это сейчас. Извините за путаницу. Я проголосовал за ваш ответ, но чувствую, что пока не могу его принять, поскольку нахожу другой ответ, который выполняет ту же задачу за сравнительно меньшее время. Но ваша программа использует меньше памяти по сравнению с этой. Спасибо за ответ!

Sambhav Khandelwal 21.02.2023 17:31
Ответ принят как подходящий

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

Миллионы целочисленных сравнений требуют очень мало вычислительного времени. Линейное решение по-прежнему будет очень быстрым и в этом случае настолько эффективным, насколько это возможно в худшем случае.

Я запускал приведенный ниже код несколько раз на своем рабочем столе и получил в среднем около 5 мс для обработки массива из 10 миллионов элементов, и во всех случаях он нашел результаты менее 10 мс.

public class Millions {

    public static int[] fillArray(int size) {
        int[] ar=new int[size];
        int randomPos=(int)(Math.random()*size);
        System.out.println("Placing missing value at position " + randomPos);
        int nextNum=1;
        for (int i=0; i<size; i++) {
            if (i==randomPos) {
                nextNum+=2;
            } else {
                if (Math.random() > 0.999995) {
                    System.out.println("Placing duplicate value at position " + i);
                } else {
                    nextNum++;
                }
            }
            ar[i] = nextNum;
        }
        return ar;
    }

    public static int missingValue(int[] ar) {
        for (int i=1; i<ar.length; i++) {
            if (ar[i]-ar[i-1]==2) return ar[i]-1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int SIZE=10000000;
        int[] ar=fillArray(SIZE);
        long start=System.currentTimeMillis();
        int missing=missingValue(ar);
        long duration=System.currentTimeMillis()-start;
        if (missing<0) {
            System.out.println("No missing value found.");
        } else {
            System.out.println("Missing value = " + missing);
        }
        System.out.println("Duration : " + duration + " ms");
    }
}

Спасибо за ответ @phatfingers. Я запустил его на онлайн-компиляторе Java и обнаружил кое-что подозрительное. Первое утверждение, которое я нахожу Placing missing value at position 8534196, указывает на номер индекса 85,34,196, но Missing value = 55. Как индекс 8534196 может быть 55?? Я не мог понять. Извините, если это глупый вопрос, но я не мог понять.

Sambhav Khandelwal 21.02.2023 16:23

Вы нашли ошибку. Я только что исправил это.

phatfingers 21.02.2023 17:22

Теперь он работает нормально. Но память, которую он занимает, составляет 73948 килобайт при работе на jdoodle.com. Его скорость хорошая, от 2 миллисекунд до 29 миллисекунд.

Sambhav Khandelwal 21.02.2023 17:27

Можно ли сделать его более эффективным для памяти?

Sambhav Khandelwal 21.02.2023 17:28

Если вы получаете данные в виде потока, то да. Вам не нужен весь набор данных сразу, чтобы сравнить два самых последних значения.

phatfingers 21.02.2023 17:33

Другие вопросы по теме