将Primitive int数组转换为list
我试图解决以下问题。 有两个大小为n的arraysA和大小为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 l1 = new ArrayList(Arrays.asList(a)); List l2 = new ArrayList(Arrays.asList(b)); for(Integer i :l2) { if(!l1.contains(i)) { System.out.println(i); } } }
我的逻辑也是O（n + 1）。 还有更好的算法吗？
谢谢
它不适用于原始数组的原因是，当给定int []时， Arrays.asList返回List
Guava在Ints类中有这个答案。 是否有一个asList方法，它将采用int []并返回List
更新
int[] a = ...; int[] b = ...; List aList = Ints.asList(a); List bList = Ints.asList(b);
以上将允许您的代码适用于int []，因为它适用于Integer []。
查看Ints API
计算每个数组的总和。 总和（B） – 总和（A）将为您提供B中的额外元素。
实际上，ArrayList的contains方法效率不高。 这个人都有一个O（n）的运行时，所以你的算法有运行时O（n ^ 2）。
我建议将一个数组放在一个HashSet中（包含O（1）的contains（）运行时）。 您可以保留其他数组，并直接遍历数组。 然后你的运行时是O（n）。
更新：从HashSet API doc ：
该类为基本操作（添加，删除，包含和大小）提供恒定的时间性能，假设散列函数在桶之间正确地分散元素。
我认为默认的Integer散列函数满足要求。
只是为了感兴趣，因为它会因为数组连接操作而有点复杂，但是另一个操作需要O(n)
- 将两个数组放入一个数组中
- 异物
- 所有相同的项目将自行删除，单个元素将是最后一个。
构造一个Set对象。 由于Set不能有重复的元素，添加所有的A，然后你可以使用Add函数找到一个在B中返回true的条目。很简单。
最快的方法是使用int[] ，使用Arrays.sort并合并结果。 我怀疑它是功课，所以我会把实际的解决方案留给自己。 这是O（n * log（n））但常量低于使用包装器对象和集合。
如果您知道值的范围有限，则可以使用BitSet。 这将检测到多个差异，仍然是O（n）
如果您知道只有一个差异，请将这些总和与@rossum建议进行比较。
您可以从两个数组构造两个Set对象，然后使用removeAll()来查找额外的元素。
PS你的方法不是你想象的O(n) 。 对于整个方法为O(n) ，循环的每次迭代必须在恒定时间内执行; 我把它作为练习让读者弄清楚是否是这种情况。
只有那些感兴趣的人，才能解决rossum逻辑的典型问题。 但是，如果我们有大数字，那么可能会出现一些溢出问题。
alg很简单，我们从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];
结果我们有了不同之处。
编辑：
哈罗德提出的更好的解决方案，我们不需要担心内存。
int result = 0; for(int i =0; i < a.length; i++) { result ^= a[i] ^ b[i]; } result ^= b[a.length];