将原始int数组转换为列表

我正在尝试解决以下问题。有两个大小为n的数组A和大小为n+1的数组B。A和B有相同的元素。B多了一个元素。查找元素

我的逻辑是将数组转换为列表，并检查B中的每个元素是否存在于a中

但是当我使用原始数组时，我的逻辑不工作。如果我使用

Integer [] a ={1,4,2,3,6,5};
Integer [] b = {2,4,1,3,5,6,7};

我的代码运行良好。

public static void main(String [] args)
{
    int [] a ={1,4,2,3,6,5};
    int [] b = {2,4,1,3,5,6,7};     
    List<Integer> l1 = new ArrayList(Arrays.asList(a));
    List<Integer> l2 = new ArrayList(Arrays.asList(b));
    for(Integer i :l2)
    {
        if(!l1.contains(i))
        {
            System.out.println(i);
        }           
    }
}

我的逻辑是0 (n+1)有没有更好的算法?

谢谢

对于基本数组不起作用的原因是数组。当给定int[]时，asList返回List而不是List。

Guava在int类中有一个答案。它有一个asList方法，该方法将接受int[]并返回List

int[] a = ...;
int[] b = ...;
List<Integer> aList = Ints.asList(a);
List<Integer> bList = Ints.asList(b);

上面的代码将允许你的代码对int[]正常工作，因为它对Integer[]工作。

查看int的API

计算每个数组的和。Sum(B) - Sum(A)将为您提供B中额外的元素

ArrayList的contains方法实际上并不是那么高效。它的运行时间为O(n)，所以你的算法运行时间为O(n^2)。

我建议将一个数组放在HashSet中(包含运行时间为O(1))。您可以保持另一个数组不变，并直接遍历该数组。那么你的运行时间是O(n)。

更新:来自HashSet API文档:

该类为基本操作(添加，删除，包含和大小)提供恒定时间性能，假设哈希函数将元素适当地分散到桶中。

我认为默认的Integer散列函数满足要求

只是出于兴趣，因为它会有点复杂，因为数组连接操作，但其他操作将采取O(n)

将两个数组放到一个数组中
<
XOR物品/gh>
所有相同的物品将被自移除，单个元素将是最后一个。

构造单个Set<Integer>对象。因为Set不能有重复的元素，所以添加a的所有元素，然后您可以使用add函数来查找b中返回true的一个条目。

最快的方法是使用int[]，使用Arrays。对结果进行排序和合并。我怀疑这是家庭作业，所以我将把实际的解决方案留给你们自己。这是O(n * log(n))，但该常数低于使用包装器对象和集合。

如果你知道值的范围是有限的，可以使用BitSet。这将检测到多个差异，并且仍然是O(n)

如果你知道有且只有一个差异，就像@rossum建议的那样比较它们的总和。

您可以从您的两个数组中构造两个Set<Integer>对象，然后使用removeAll()来查找额外的元素。

注:你的方法不是O(n)，因为你似乎认为。对于整体方法为O(n)，循环的每次迭代必须在常数时间内执行;

我把它留给读者作为练习来弄清楚情况是否如此。

仅供感兴趣的人参考，典型的解决方案以rossum逻辑为主。但如果我们有很大的数字，那么可能会出现一些溢出问题。
算法很简单，从w个零值开始，从一个数组中减去另一个数组中的元素，然后在其中添加元素，最后添加n+1元素。
这将在O(n) (n是n+1)

我假设数组b有更多的元素。

long result = 0; for(int i =0; i < a.length; i++) { result -= a[i]; result += b[i]; } result += b[a.length];
在结果中我们有我们的差异。
编辑:

harold提出的更好的解决方案，我们不需要担心内存。

int result = 0; for(int i =0; i < a.length; i++) { result ^= a[i] ^ b[i]; } result ^= b[a.length];

如果你想转换一个int数组(不是Integer)，使用IntStream:

int[] arr = {15, 13, 7, 4, 1, 5, 19, 18, 7, 7, 12, 15}; List<Integer> arrayList = IntStream.of(arr).boxed().collect(Collectors.toList()); System.out.println(arrayList);

相关内容

最新更新

热门标签：