Я задаю этот вопрос в связи с этим вопросом, опубликованным несколько месяцев назад.
В настоящее время в приложении, над которым я работаю, я получаю серию чисел, где числа могут отсутствовать и дублироваться, но упорядочены по возрастанию.
Было две проблемы.
Если дубликатов не было, найти недостающее число было довольно легко, используя метод, предложенный в принятом ответе на вопрос об упоминании.
Но если есть дубликаты, этот подход больше не работает.
Как я могу решить проблему? Никакая логика, кажется, не работает. И даже если бы это было (используя цикл), это было бы неэффективно.
ПРИМЕЧАНИЕ. Я также искал некоторые библиотеки, но не смог их найти.
Как мне это сделать? без петель? Данные моего приложения должны обновляться каждые 2-3 секунды, поэтому такой подход не очень хорош, не так ли?
Извините, но я что-то упустил. Дубликаты необходимы для правильной работы приложения и не могут быть устранены.
Вы не должны удалять дубликаты из фактической полезной нагрузки. Вы должны удалить дубликаты из временной копии этих данных, чтобы алгоритм работал.
Нет смысла удалять дубликаты (операций O(n)) только для того, чтобы оптимизировать поиск пропущенных чисел. Вы уже перебираете элементы, так что можете искать пропущенное число, пока делаете это. Я не думаю, что в этом случае есть способ добиться большего, чем O(n).
Это действительно зависит от вашего конкретного варианта использования. Если несколько тысяч чисел отсутствуют, вы можете хранить диапазоны вместо каждого числа по отдельности.
Похоже, вам просто нужно выполнить бинарный поиск, но ваша формулировка не дает понять, что вы на самом деле пытаетесь сделать. Пожалуйста, включите минимальный воспроизводимый пример.
Насколько я знаю, нет никакого способа обнаружить пропущенное число в списке, кроме перебора.
Если ваш массив отсортирован, он должен выглядеть примерно так:
[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 хорош для небольших диапазонов. Но у меня есть миллионы чисел в моем массиве. это не эффективно
Я просто попытался посмотреть, насколько я могу разбить задачи, используя 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
, первое выражение в выводе, почему оба числа одинаковы?
Вы читали код? Они создали массив из 50 мл элементов в верхней части файла main. System.out.println("Problem! - "+current+" "+next);
Вы видите, что текущий элемент массива (390
) равен следующему элементу массива (390
). Или текущий элемент массива (390
) не равен на 1 меньше, чем следующий элемент массива (392
). поэтому пропущено число (391
). Смысл этого кода в том, чтобы показать, что цикл завершился за 60 мс, а Runnable завершился за 49 мс. Вы, кажется, считаете, что петля - это плохо. Они доказывают, что это не так.
Я, вероятно, запутался со вторым подходом, но то, что я действительно хотел сделать, это что-то вроде использования runnable, разбить его на списки определенной длины и обработать каждый. Проблема со вторым подходом, который я не смог решить, заключается в том, что в конце дня он снова «объединит» разбитые части и обработает уже обработанные элементы массива.
проблема в том, что текущий элемент и следующий дублируются, и на следующей итерации текущий элемент не на 1 меньше, чем следующий элемент, поэтому две ошибки приходят одна за другой
Я получаю это сейчас. Извините за путаницу. Я проголосовал за ваш ответ, но чувствую, что пока не могу его принять, поскольку нахожу другой ответ, который выполняет ту же задачу за сравнительно меньшее время. Но ваша программа использует меньше памяти по сравнению с этой. Спасибо за ответ!
Бинарный поиск выигрывает от того, что он может разрезать проблемное пространство пополам, а затем удалить одну из половин. В этом случае любая половина, которая содержит как отсутствующее значение, так и дубликат, неотличима от той, которая их не содержит, независимо от того, сколько существует дополнительных дубликатов, поэтому вам придется обрабатывать обе половины.
Миллионы целочисленных сравнений требуют очень мало вычислительного времени. Линейное решение по-прежнему будет очень быстрым и в этом случае настолько эффективным, насколько это возможно в худшем случае.
Я запускал приведенный ниже код несколько раз на своем рабочем столе и получил в среднем около 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?? Я не мог понять. Извините, если это глупый вопрос, но я не мог понять.
Вы нашли ошибку. Я только что исправил это.
Теперь он работает нормально. Но память, которую он занимает, составляет 73948 килобайт при работе на jdoodle.com. Его скорость хорошая, от 2 миллисекунд до 29 миллисекунд.
Можно ли сделать его более эффективным для памяти?
Если вы получаете данные в виде потока, то да. Вам не нужен весь набор данных сразу, чтобы сравнить два самых последних значения.
Кажется, вы могли бы просто начать с удаления дубликатов, а затем применить предыдущий алгоритм. Поскольку числа упорядочены, удаление дубликатов имеет эффективность алгоритмов O (n).