韩槑槑

求两个集合的交集 要求时间复杂度为 O(m+n) 或 O(m*n)

字数统计: 273阅读时长: 1 min
2018/12/13 Share

为什么会写这个

平时比较爱逛论坛,有一天发现一篇文章
原网址为:https://www.v2ex.com/t/466422
这篇文章吐槽一个三年经验的 PHP 不会写这个算法题
为了避免三年后我也被挂在论坛吐槽所以就先练习下 -_-!!

O(m*n)

这个比较简单就是两个循环嵌套遍历判断是否相同即可

1
2
3
4
5
6
7
8
9
10
11
12
13
$m = [1, 2, 3, 4];
$n = [1, 4, 7, 9];
$intersection = [];

foreach ($m as $m_v) {
foreach ($n as $n_v) {
if ($m_v === $n_v) {
$intersection = $m_v;
}
}
}

return $intersection;

O(m+n)

这个解法就是通过定义两个数组的指针来进行循环
最差的结果就是 O(m+n)
但是有一个前提就是这两个数组必须是排序过后的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
$m = [1, 2, 3, 4];
$n = [1, 4, 7, 9];
$intersection = [];

// 获取两个数组的长度
$length_m = count($m);
$length_n = count($n);

// 定义两个指针
$i = $j = 0;
$intersection = [];

while ($i < $length_m && $j < $length_n) {
if ($m[$i] === $n[$j]) {
$intersection[] = $m[$i];
} else if ($m[$i] < $n[$j]) {
$i++;
} else {
$j++;
}
}

return $intersection;

CATALOG
  1. 1. 为什么会写这个
  2. 2. O(m*n)
  3. 3. O(m+n)