java - 组合来自 2 个数组的唯一整数的最快方法

Question

如果我有 2 个数组:

arr1 = {9,8}
arr2 = {13,12,10,9,8}

我想得到:

{13,12,10}

并给定数组:

arr1 = {23,22,21,20,19,18,17,16}
arr2 = {21,17}

结果将是:

{23,22,20,19,18,16}

所以基本上我获得的是 arr1 或 arr2 中的数字，但不是两者。

• 2 个数组的长度可能不同。
• 2个数组按降序排列，最后的数组也必须有这个属性。
• 这已经进行了数百万次，所以我正在尽我所能减少/防止对象分配。这就是我不使用集合来完成这项工作的原因。

Answer 1

由于数组已排序，它们之间的重叠很重要 - 您可以非常快速地处理单个数组中的非重叠部分，而无需检查另一个数组。

9 8 7 5
     6 4 3 2

例如9,8,7 可以直接从数组 1 中获取，然后中间部分需要更多注意，然后您可以直接从数组 2 中获取 4,3,2。这将有助于了解输入的非重叠部分是否是可能显着或不显着。

对于中间部分，您只需要重复从每个数组中取下一个未处理元素的最大值(并删除重复项)。

您将需要一个数组来存储结果 - 一种方法是分配一个足够大的数组来容纳两个输入数组，最坏的情况是，然后执行 System.arrayCopy()放入一个大小合适的新数组中，或者只计算实际元素的数量。另一种方法是使用 ArrayList，然后根据需要执行 toarray。