logo标签列表

将原始的int数组转换为列表

javaalgorithm
4
我将尝试解决以下问题。有两个数组A和B，大小分别为n和n+1。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);
        }           
    }
}

我的算法时间复杂度为O(n+1)，是否有更好的算法。

谢谢。

1
你的逻辑是n*m，基本上是平方级别(n^2)，因为对于数组的每个元素，你都要在第二个数组中进行搜索，在字典/映射的情况下，搜索速度会更快，但在使用列表的情况下，它是n^2。 - sll
9个回答
20

这段代码不能用于原始数组的原因是，Arrays.asList 在给定 int[ ] 时返回的是 List<Integer[ ]>，而不是 List<Integer>。

Guava 中的Ints类提供了解决方案。它具有一个asList方法，可以将 int[ ] 转换为 List<Integer>

更新

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

以上将允许您的代码像对Integer[]一样对int[]正常工作。

查看Ints API

我修改了我的代码，如下：List<Integer[]> l1 = new ArrayList(Arrays.asList(a)); List<Integer[]> l2 = new ArrayList(Arrays.asList(b)); for(Integer[] i :l2) { if(!l1.contains(i[0].intValue())) { System.out.println(i); }
} - javaMan
已更新。请注意，我使用的是Ints.asList而不是Arrays.asList。这是Guava库函数，因此您需要包含guava jar。 - John B
不错的发现。我过去用过它，但是现在找起来花费了很长时间。记住，在所有相应的类中都有类似的方法-长整型、浮点型、双精度等。 - spaaarky21
太棒了！这就是我正在寻找的。 :) 谢谢。 - ViliusK
6

计算每个数组的总和。Sum(B) - Sum(A) 将会告诉你B数组中多出来的元素。

很好。这假设只有一个元素不同。但如果是这种情况，它可以很好地工作，并且确实是O(n)。 - John B
对于整数和长整数，而不一定是布尔值、双精度和浮点数。 - Matthew Farwell
@MatthewFarwell 布尔值也可以使用，无论是“+ 是异或”解释还是“true 是 1”解释。 - harold
3

ArrayList的contains方法实际上并不是很高效。仅这一步的运行时间为O(n)，因此您的算法的运行时间为O(n^2)。

我建议将一个数组放入HashSet中（其中contains()的运行时间为O(1)）。您可以将另一个数组保留原样，并直接遍历该数组。然后，您的运行时间为O(n)。

更新： 从HashSet API文档：

假设哈希函数在桶中适当分散元素，此类基本操作（添加、删除、包含和大小）的性能均为常数时间。

我认为默认的Integer哈希函数符合要求。

它真的会是O(n)吗？因为HashMaps的contains方法并不完全是O(n)。O-ness取决于元素数量与桶数量之间的比例。 - John B
@John B：我认为由于数组具有不同的值，因此不会创建任何桶。 - sll
@venje 并不一定是真的。根据 equals / hashCode 协议，不同的值可能具有相同的 hashCode。虽然每个 int 值具有唯一的 hashCode 可能是一个安全的假设（因为 hashCode 返回 int），但对于像 long 这样的东西来说并不是真的，我认为这不是一个安全的假设。话虽如此，我不知道 O-因子是否真的是问题所在。 :) - John B
2

这只是出于兴趣，因为由于数组串联操作会有点复杂，但其他操作将需要 O(n)

  1. 将两个数组放入一个单一的数组中
  2. 异或 项目
  3. 所有相同的项目都将被自动删除，仅剩下单个元素。
1

只针对那些感兴趣的人，这是一个典型的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];

最终结果中我们有差异。

编辑：

哈罗德提出了更好的解决方案，我们不用担心内存问题。

int result = 0;

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

result ^= b[a.length];
溢出并不重要，结果仍然正确 - 或者您可以使用异或运算，避免溢出。 - harold
1
如果您想转换一个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);
1

你可以从两个数组中构造出两个Set<Integer>对象，然后使用removeAll()方法来找到多余的元素。

P.S. 你的方法并不像你想象的那样是O(n)的。为了使整个方法具有O(n)的复杂度，循环的每次迭代都必须在常数时间内执行。我把这留给读者自己去琢磨是否达成了这个目标。

1
那么O是什么？我认为是O(n^2)（n平方）。 - John B
@aix，我认为我的算法是O(n)的。因为我只循环遍历了B中的所有元素一次。当它完成时，我们就完成了。我错了吗？ - javaMan
int[] a = {1,4,2,3,6,5}; int[] b = {2,4,1,3,5,6,7}; Set<Integer> s1 = new HashSet(); Set<Integer> s2 = new HashSet(); s1.add(a); s2.add(b); s2.removeAll(s1); Object[] c = s2.toArray(); System.out.println(c[0]); - javaMan
@ravi，这可能是O(n^2)，因为contains()本身可能是O(n)，例如如果使用ArrayList。 - Peter
1
构建一个单一的 Set<Integer> 对象。由于 Set 不能有重复元素，因此将 A 中的所有元素添加进去，然后使用 Add 函数在 B 中查找返回 true 的那个元素即可。非常简单易懂。
1
最快的方法是使用int[]，使用Arrays.sort并合并结果。我怀疑这是作业，所以我会把实际解决方案留给你自己。这是O(n*log(n))，但常数比使用包装器对象和集合低。
如果你知道值的范围是有限的，你可以使用BitSet。这将检测到多个差异，仍然是O(n)。
如果你知道只有一个差异，请像@rossum建议的那样比较总和。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接