如何查找在动态数组中添加或删除的最新元素

Question

我在循环中得到一个输入数组，其中包含按排序顺序排列的数字。在每次迭代中，输入数组将添加或删除任何一个数字（输入数组中没有重复项）。例子

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

注意：我有一个解决方案，我可以使用映射或不同的数组并将输入数组复制到新数组中，然后从下一次迭代开始我将迭代输入数组并将输入数组的元素与新数组进行比较，新数组中不存在的元素是添加的元素；新数组中存在但输入数组中不存在的是删除的那个。我正在寻找一种在 space 和时间方面具有最优化逻辑的更好方法。

Answer 1

下面给出的是最简单的方法之一：

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.

Answer 2

如果数组始终排序并且输入仅在一个地方发生变化，那么如果您在每次迭代时都可以访问旧数组和新数组，则高效的算法可以搜索数组之间的第一个不同元素在 O(log n) 时间内使用二进制搜索。如果 mid 指向不同的元素，则查看左半部分；否则，在右边。

如何查找在动态数组中添加或删除的最新元素

how to find latest element added or deleted in dynamic array

java

algorithm

dynamic-arrays

data-structures