仔细回想了一下, 大一下开始, 就再也没有刷过题. 然而眼见马上就要实习了, 几个提前去面试的同学回来说应聘居然考的是大一那会的算法… 好吧, 虽然算法很重要, 但是计算机不应该使用来解决问题的吗? 我还以为面试会针对一些具体的开发场景或者开发框架问一些问题么…

算了, 都一样. 算法到哪里都用得着. 那么今天就开始回坑刷题, 但毕竟手上还压着两个项目没做, 所以权当是消遣, 娱乐局…

LeetCode 287 Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

桶排法计数

第一个反应就是用空间换时间, 用桶排法的思想, 创建一个相同长度的 vector<int> 来记录数组中出现的数字个数, 然后遍历一遍数组.

1
2
3
4
5
6
7
8
9
10
11
12
int findDuplicate(std::vector<int> &nums) {
    int size = nums.size();
    std::vector<int> vec(size, 0);
    for (int i = 0; i < size; i++) {
        if (vec[nums[i]] == 1) {
            return nums[i];
        } else {
            vec[nums[i]] = 1;
        }
    }
    return 0;
}

这种写法很简单, 时间复杂度 O(N). 程序也简单, 5分钟就能写完. 当然结果也不出所料:

执行用时分布图

虽然内存消耗也不小. 但毕竟功能实现了…

因为这里新开一了一个容器, 导致内存占用较大. 如果不新开内存也是有办法的, 那就是直接对其排序, 然后遍历一遍这个有序数组, 把每一个元素都和下一个元素比较是否相等. 排序的算法也很多, 但不管用什么排序算法, 时间复杂度一定会大于等于 O(N). 个人一项主张用空间换时间, 主要可能是换 CPU 没有内存条方便吧:-)

环链表查询

刚才的角度是从整体看整个数组存储的数据结构就是一个数组. 但是如果换个角度, 这个数组内存储的这些数据是一个 环链表 的话, 就全部都不一样了. 把每一个元素看成是链表的一个节点, 把每一个数组的下标看成是链表节点的地址(索引), 再把每一个数组内储存的值看成是节点的 next, 以 [1,3,4,2,2] 为例, 整个链表的上帝视角应该是这样的:

环形链表

数组内重复的那个元素其实就是环链表的起始环点. 设置两根指针, 一根 slow, 一根 fast, slow 每次前进一个节点而 fast 每次前进两个. 当他们相遇的时候, slow 从起点出发, fast 从相遇点出发, 一次走一步. 再次相遇的时候就是起始环点.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int findDuplicate(std::vector<int> &nums) {
    int slow = nums[0];
    int fast = nums[nums[0]];
    //寻找相遇点
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    //slow 从起点出发, fast 从相遇点出发, 一次走一步
    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

证明如下:

环形链表的证明

这种算法时间复杂度还是 O(N), 空间复杂度也降低了. 最后运行时间跟上面一样 16ms, 内存少了 1MB. 没错,,,,费老鼻子劲, 就少了 1MB 内存…

暴力搜索是最快的???

实在没忍住, 看了一眼 0ms, 2ms 的解法, 意外发现居然是暴力解法…那些看上去时间复杂度是 O(N2) 的算法, 反而是最快的. 仔细想了下, 要不就是测试数据设置不合理, 循环前几次就得到答案, 要不就是后台解释器对暴力循环妖魔般优化了. 不管怎么说, 是在下输了…告辞