分析一个算法面试题

Posted by 王灿辉 on 2019-05-21

题目

在一个整数序列中找出所有和为 sum 的两个整数的组合打印出来,两个整数排序不同的只算作一组

解答

这个题目很简单,大多数人不假思索就能写出下面的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>

/* 时间复杂度 O(n^2) */
void fun1(int a[], int len, int sum) {
    for (int i = 0; i < len; i++) {
        for (int j = i; j < len; j++) {
            if (a[i] + a[j] == sum)
                std::cout << a[i] << ", " << a[j] << std::endl;
        }
    }
}

int main(){
    int a[] = {1,2,4,6,7,8,9};
    fun2(a, 7, 10);
    return 0;
}

但是,我们稍加分析就能得知,这种算法的时间复杂度为O(n^2),因为它通过两层循环将序列中的整数进行两两对比。

思考还有更好的解决方法吗?有的。

如果我们取出序列中的一个整数 num,那么我们希望能够在序列中找到的另一个值为 sum - num 的数,所以我们可以使用一个 hash 表来存储 sum - numnum 组成的键值对。我们知道 hash 表的时间复杂度的常数级的,所以当我们拿到一个整数时,能够很快地通过查 hash 表知道有没有另一个数能与之组成 sum。

我们可以借助 STL 中的 unordered_set 和 unordered_map 来完成,它们的底层都是通过 hash 表实现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <unordered_map>

/* 时间复杂度 O(n) */
void fun2(int a[], int len, int sum) {
    std::unordered_map<int, int> map;
    std::unordered_map<int, int>::const_iterator got;
    for (int i = 0; i < len; i++)
    {
        got = map.find(a[i]);
        if (got == map.end()) /* 没找到 */
            map.insert({sum-a[i], a[i]});
        else
            std::cout << got->second << ", " << got->first << std::endl;
    }
}

int main(){
    int a[] = {1,2,4,6,7,8,9};
    fun2(a, 7, 10);
    return 0;
}



赞赏支持
微信赞赏
微信赞赏
支付宝
支付宝