A = [9, 1, 4, 2, 5] k个整数
B = [3, 1, 8, 7, 6, 5] n个整数
Intersection => [1, 5]

复杂度理论证明

问题复杂度下限

设A为较小的列表，B为较大的列表，则k<n。

对于A中的每个元素都要查看B中是否有相同元素。查看B中是否有相同元素的时间复杂度至少为O(1)，A需要迭代每个元素，所以问题复杂度时间下限为O(k)。

根据复杂度关系，空间复杂度小于等于时间复杂度^[1][2]，所以该问题的空间复杂度下限小于O(k)——这等于没说，空间复杂度可能是O(1)、[latex]O(\log k)[/latex]，也可能因为时间复杂度的提升而提升，比如[latex]O(k^2)[/latex]。

下文会处理要求给出空间复杂度为O(1)时的算法，这里先证明这样的算法的时间复杂度下限。

O(1)空间的算法的时间下限

答案是没有一般规律，必须联系具体问题想出具体算法。^[3]可能一个算法在处理时间上很高效，但内存上不高效。可能可以想出一个算法，改进了空间复杂度并保持时间复杂度不变。

数组元素不重复：空间O(min(n,k))，时间O(n+k)

把数组放入散列表，获得O(1)的查找时间。
[code lang=”java”]
/**
* 时间复杂度 O(size(a)+size(b))。空间复杂度O(size(b))。
*
* @param a
* @param b
* @return
*/
private static List<Integer> getUniqueIntersection(List<Integer> a, List<Integer> b)
{
assert new HashSet<Integer>(a).size() == a.size();
assert new HashSet<Integer>(b).size() == b.size();

if (a.size() < b.size())
return getUniqueIntersection(b, a);

// 设a的长度为k，b的长度为n。
List<Integer> intersection = new ArrayList<Integer>();

HashSet<Integer> set = new HashSet<Integer>(b); // 时间O(n)

for (Integer n : a) // 时间O(k)
{
if (set.contains(n)) // O(1)
intersection.add(n);
}
return intersection;

// ==Vector和ArrayList区别==
// 1、Vector是线程安全的，ArrayList不是。
// 2、数据增长:当需要增长时,Vector增长为原来一培，而ArrayList是原来的一半。

}
[/code]

数组元素不重复：空间O(1)，时间[latex]O((n+k) \log(\operatorname{min}(n,k)))[/latex]

先排序，然后进行二分查找。排序算法可用堆排序。

可令参数b为较小的一个列表，则时间复杂度的log项变得较小。
[code lang=”java”]
/**
* 不需要额外空间的算法。
*
*/
private static List<Integer> getUniqueIntersectionO1Memory(List<Integer> a, List<Integer> b)
{
assert new HashSet<Integer>(a).size() == a.size();
assert new HashSet<Integer>(b).size() == b.size();

if (a.size() < b.size())
return getUniqueIntersectionO1Memory(b, a);

// 设a的长度为k，b的长度为n。

List<Integer> intersection = new ArrayList<Integer>();
sort(a);
// 堆排序时间O(k log k)，空间O(1)；
// 计数排序时间O(n+m)，空间O(n+m)。

for (Integer n : b) // O(n log k)
{
int r = Collections.binarySearch(a, n); // O(log k)
if (r > -1)
intersection.add(n);
}
return intersection;
}
[/code]

数组元素有重复：空间O(min(n,k))，时间O(n+k)

改用HashMap保存元素及出现次数，每出现一次匹配出现次数减一。
[code lang=”java”]
private static List<Integer> getDuplicateIntersection(List<Integer> a, List<Integer> b)
{
if (a.size() < b.size())
return getDuplicateIntersection(b, a);

// 设a的长度为k，b的长度为n。
List<Integer> intersection = new ArrayList<Integer>();

HashMap<Integer, Integer> set = new HashMap<Integer, Integer>();
for (Integer n : b)// 时间O(n)，空间O（n）
{
if (set.containsKey(n))
set.put(n, set.get(n) + 1);
else
set.put(n, 1);
}

for (Integer n : a) // 时间O(k)
{
if (set.containsKey(n)) // O(1)
{
intersection.add(n);
int count = set.get(n);
assert count > 0;
if (–count > 0)
set.put(n, count);
else
set.remove(n);
}
}

// 总时间O(n+k)，总空间O(n)。
return intersection;
}
[/code]

数组元素有重复：空间O(1)，时间[latex]O(n\log n+k\log k)[/latex]

排序a、b两个列表，然后对两个列表顺序查找。
[code lang=”java”]
private static List<Integer> getDuplicateIntersectionO1Space(List<Integer> a, List<Integer> b)
{
List<Integer> intersection = new ArrayList<Integer>();

// 设a的长度为k，b的长度为n。

sort(a); // O(k log k)
sort(b); // O(n log n)

int ia = 0;
int ib = 0;
while (ia < a.size() && ib < b.size()) // O(min(k,n))
{
while (a.get(ia) < b.get(ib))
{
ia++;
if (ia == a.size())
return intersection;
}
assert a.get(ia) >= b.get(ib);
while (a.get(ia) > b.get(ib))
{
ib++;
if (ib == b.size())
return intersection;
}
assert a.get(ia) <= b.get(ib);
if (a.get(ia) == b.get(ib))
{
intersection.add(a.get(ia));
ia++;
ib++;
}
}
return intersection;

// 总的时间复杂度为O(k log k+n log n+min(k,n))
// 如果k>n，则O(k log k+n log n+n)=O(k log k+n(1+log n))=O(k log k+n log n)
// 如果k<n，则O(k log k+n log n+k)=O(k(1+log k)+n log n)=O(k log k+n log n)

}
[/code]

任何算法的时间复杂度必然大于等于其空间复杂度。

参考资料

. Find intersection of two arrays without duplicates. Code Review. 2015-01-15 [].

参考资料

1. . Relation of time complexity and space complexity. stackoverflow. 2011-08-22 [2015-01-17].↑
2. 证明极为简单：你要多少空间就得花费多少时间来获得它。↑
3. . Decrease space complexity, how will time complexity increase?. Computer Science. 2015-01-17 [2015-01-18].↑