VPF::Как найти, какой элемент был удален в массиве

Metalex

Дата 13.11.2014, 15:24 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет

Простая задачка, на которую я тем не менее не смог ответить. Есть массив интов или байтов, мы в нем удаляем какой-то элемент путем формирования нового массива без этого элемента. Массивы неотсортированы. Как имея эти 2 массива, узнать, какой элемент был удален? Естественно, без перебора, нужно наиболее эффективное/быстрое решение.
Задача общая, но если брать контекст языка, то берем java. Может есть какие-то стандартные методы, о которых я не знал.

--------------------

Don't let the system get you down.

Akina

Дата 13.11.2014, 15:32 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

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

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

Metalex

Дата 13.11.2014, 16:37 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет

Akina, спасибо, суть понял, но детали пока не очень. Например, мы берем средний индекс first + (last - first) / 2. И.. что нам дает равенство или неравенство элементов из массивов по этому индексу? Ведь мы не знаем, в какую сторону от него будет несовпадение элементов - то ли влево, то ли вправо.

--------------------

Don't let the system get you down.

Akina

Дата 13.11.2014, 16:42 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата(Metalex @ 13.11.2014, 17:37

)

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

ТО есть, ты не знаешь, какой из массивов исходный, а какой результирующий? Я тебе подскажу - исходный длиннее...

--------------------

Metalex

Дата 13.11.2014, 16:48 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет

Akina, это ясно. Ок. Есть source[middle] == output[middle]. Элементы равны/неравны. Что это дает? Может я неправильно выражаюсь.

--------------------

Don't let the system get you down.

Metalex

Дата 13.11.2014, 17:10 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет

Akina, кажется дошло. Попробую реализовать

--------------------

Don't let the system get you down.

Metalex

Дата 13.11.2014, 18:17 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет

Вдруг кому пригодится

Код


import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Random;
import java.util.Set;

public class C001BinarySearch {

    private static final int TEST_COUNT = 10000;
    private static final int MAX_ARRAY_LENGTH = 500;
    private static final int MAX_NUMBER_IN_ARRAY = 500;

    public static void main(String[] args) {
        for (int i = 0; i < TEST_COUNT; i++) {
            run();
        }
        System.out.println(TEST_COUNT + " тестов завершено");
    }

    private static void run() {
        Random r = new Random();
        Set<Integer> sourceSet = new LinkedHashSet<>();
        for (int i = 0, length = r.nextInt(MAX_ARRAY_LENGTH); i < length; i++) {
            sourceSet.add(r.nextInt(MAX_NUMBER_IN_ARRAY));
        }
        if (sourceSet.size() < 2) {
            return;
        }
        Integer[] source = sourceSet.toArray(new Integer[0]);
        // System.out.println(Arrays.toString(source));

        int elementToDel = source[new Random().nextInt(source.length)];
        Integer[] output = new Integer[source.length - 1];
        for (int i = 0, j = 0; i < source.length; i++) {
            if (source[i] == elementToDel) {
                continue;
            }
            output[j] = source[i];
            j++;
        }
        // System.out.println(Arrays.toString(output));

        int deletedElement = findDiffRecursion(source, output, 0,
                source.length - 1);
        if (deletedElement != elementToDel) {
            System.out.println(Arrays.toString(source));
            System.out.println(Arrays.toString(output));
            System.out.println("Ошибка при нахождении " + elementToDel);
        }
    }

    private static int findDiffRecursion(Integer[] source, Integer[] output,
            int first, int last) {
        if (last - first == 1) {
            if (source[first] == output[first]) {
                return source[last];
            } else {
                return source[first];
            }
        }
        // вычисляем средний индекс, во избежание переполнения при очень
        // больших числах, не используем (first + last) / 2
        int i = first + (last - first) / 2;
        // System.out.println("inside finder: [first=" + first + "], [i=" + i
        // + "], [last=" + last + "]");
        if (source[i] == output[i]) {
            // если элементы равны, то смещение произошло правее
            return findDiffRecursion(source, output, i, last);
        } else {
            // если не равны, то левее
            return findDiffRecursion(source, output, first, i);
        }
    }
}

--------------------

Don't let the system get you down.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »