как найти последний элемент, добавленный или удаленный в массиве Dynami c - PullRequest
Новая
       95

как найти последний элемент, добавленный или удаленный в массиве Dynami c

0 голосов
/ 13 апреля 2020

Я получаю входной массив в l oop, который содержит числа в отсортированном порядке. на каждой итерации входной массив будет либо добавляться, либо удаляться с любым одним номером (без дубликатов во входном массиве) Пример 

1st iteration: Input Array [3,4,8,19]
2nd iteration: Input Array [3,4,5,8,19]
Output: 5 added
3rd iteration: Input Array [3,4,5,8,19,40]
Output: 40 added
4th iteration: Input Array [3,5,8,19,40]
Output: 4 deleted
5th iteration: Input Array [1,3,5,8,19,40]
Output: 1 added

Примечание: У меня есть решение, в котором я могу взять карту или другой массив и скопировать входной массив в новый массив, а затем со следующей итерации я собираюсь повторить входной массив и сравнение элементов входного массива с новым массивом, добавленный элемент, отсутствующий в новом массиве; и тот, который присутствует в новом массиве, но не присутствует во входном массиве, является удаленным. Я ищу лучший подход с наиболее оптимизированной логикой c с точки зрения пространства и времени.

Ответы [ 2 ]

0 голосов
/ 13 апреля 2020

Если массив всегда сортируется, а входные данные изменяются только в одном месте, то, если у вас есть доступ к старому и новому массиву на каждой итерации, эффективный алгоритм может искать первый различный элемент между массивами в O(log n) время с бинарным поиском. Если середина указывает на разные элементы, посмотрите в левую половину; в противном случае справа.

0 голосов
/ 13 апреля 2020

Ниже приведен один из самых простых способов: 

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int first[] = { 3, 4, 8, 19 };
        int second[] = { 3, 4, 5, 8, 19 };
        int diff = Arrays.stream(second).sum() - Arrays.stream(first).sum();
        System.out.println(Math.abs(diff) + (diff > 0 ? " added." : diff < 0 ? " deleted." : ""));
    }
}

Вывод: 

5 added.

Демонстрация: 

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[][] testArrs = { 
                { 3, 4, 8, 19 }, 
                { 3, 4, 5, 8, 19 }, 
                { 3, 4, 5, 8, 19, 40 }, 
                { 3, 5, 8, 19, 40 },
                { 1, 3, 5, 8, 19, 40 } };
        int i, diff = 0, lastSum = Arrays.stream(testArrs[0]).sum(), currentSum;

        for (i = 1; i < testArrs.length; i++) {
            currentSum = Arrays.stream(testArrs[i]).sum();
            diff = currentSum - lastSum;
            System.out.println(Math.abs(diff) + (diff > 0 ? " added." : diff < 0 ? " deleted." : ""));
            lastSum = currentSum;
        }
    }
}

Выход: 

5 added.
40 added.
4 deleted.
1 added.
...