casyup.me@outlook.com

0%

leetcode/FindtheDuplicateNumber

Posted on

Find the Duplicate Number

my solution

我的做法偏向于数学, 我是这样思考的: n 个数的话, 原本的总和 Sn 是可以直接求出来的. 这个原本的总和和实际总和(Sn1)的差距就是重复数组所造成的影响(Sn2), 我也可以通过 O(n) 来算出有多少个数字不存在, 名为 cnt. 因为重复数字只会有一个, 其间的差 (Sn1 + Sn2 - Sn) / cnt 的结果就是重复的数字. 比如:

6 7
1 3 3 | 2 + 1 = 3
6 7
2 2 3 | 1 + 1 = 2

10 8
1 2 2 3 | 4 - 2 = 2
10 9
2 2 2 3 | 9 + 1 + 4 - 10 / 2 = 2

假设数字[1, 3, 3] 其 Sn = 6, Sn1 = 7, Sn2 = 2, 则由之前的公式可得: (7 + 2 - 6) / 1 = 3.

其余案例依旧如此. 代码如下 : 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        long long sum = 0;
        int cnt = 0;
        for (int i = 1; i <= nums.size(); ++i) {
            sum += nums[i - 1];
            if (find(nums.begin(), nums.end(), i) == nums.end()) {
                ++cnt;
                sum += i;
            }
        }

        return (int)((sum - (1 + nums.size()) * nums.size() / 2) / cnt);
    }
};

这是个 O(n) 复杂度的算法, 但是其中那个 find 很耗时, 应该是算法的核心瓶颈.

并且 nums.size()) * nums.size() / 2 要注意一下, 这里我假设是从左往右的, 但是如果计算机不这么做, 可能会有问题.

the best solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if (nums.size() < 2)
            return - 1;

        int slow{ nums[0] };
        int fast{ nums[nums[0]] };

        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        fast = 0;
        while (fast != slow) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return fast;
    }
};

这和之前我做过的一道链表题的解法十分相似, 思路是这样的: 一个人走得快, 另一个人走得慢. 快的人的距离一直是慢的人的两倍, 所以一开始 slow 是 nums[0], 而并非 0. 因为 0 和 1 的差距和 1 和 2 的差距虽然都只有1, 但前者并没有倍数关系. 而当走了 n 步时(fast 走了 2n步) 两人碰撞. 此时 fast 再重新开始, 以同样的速度开始行走, 那么 n 步后, 一定会相遇(我不太确定是否一定是 n 步, 但最多 n 步). 此时 slow 和 fast 的位置肯定是不同的 (while 的条件保证了其不同) 所以最后的值就是重复的数字. 之所以需要两次, 是因为第一次的结果可能会出现偶然的情况, 比如都指向同一个数字.

第一次的循环结束, 意味着有两个下标指向的数值是相同的(偶然情况会指向同一个下标). 也就是说, 在第一次结束时, 答案就已经有可能得到了

将标注的代码增加后, 也可以得到答案.

而第二次循环是为了规避偶然情况, 比如 [3,1,3,4,2] 到第一次循环结束 slow 是 4, fast 是 3. 刚好, 其实他们指向的是同一个数字, 针对这种情况, 就有了第二次循环. 而之所以第二次循环从 0 开始, 是因为这里需要的是步数一致. 一定会得到答案么? 再仔细想想这个例子, 其循环周期为: 3, 4, 2, 3, 4, 2… 当然, 第二次是以 2 开始的, 所以是 2, 3, 4…

emm… [挠头…]

这个算法有两个前提条件:

  1. 数组中的数字都能当作下标, 也就是不超过数组长度
  2. 重复的数字只能有一个, 不然可能会造成死循环