政子的博客

技术|学习|随笔

LeetCode-Ect Squares

这道题不允许使用超过 O(1)空间复杂度，而且不允许修改原数组，所以不能用 set、map 或者排序，需要另辟蹊径。

在 solution 中找到一个不错的办法——快慢指针法。因为数字的范围是 1 到 n-1 ，所以可以将数组中的索引 0-n 和实际存的数字对应起来。

  • 首先，定义两个指针，快指针速度为 2，慢指针速度为 1，先让两个指针相遇，得到相遇点。
  • 然后，一个指针停在相遇点，另一个指针从 0 开始，这次两个指针的速度均为 1。
  • 最后两个指针再次相遇的地方即为重复的数字。

快慢指针的原理来自 Leetcode 中142. Linked List Cycle II，由于有重复数字存在，所以在数组中不断通过索引-数值搜索一定会进入循环，而使用快慢指针，就可以判断是否存在环（在题目中一定存在）以及能够确定一个相遇点，这个相遇点的位置和入口点的距离就等于整个数组开始点到环入口的距离（可以用简单的推导证明，证明可见Discuss），所以再次将一个指针移到开头，并同步前行，再次相遇的地方就是环的入口，即为重复数字的索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow=nums[0],fast=nums[nums[0]];
        while(fast!=slow){
            slow=nums[slow];
            fast=nums[nums[fast]];
        }
        slow=0;
        while(fast!=slow){
            slow=nums[slow];
            fast=nums[fast];
        }
        return slow;
    }
};

还有一种很巧妙的方法——Bit-Manipulation。原理也比较精妙，遍历一个 int 中的每一个比特（设置 int 中某个比特为 1），然后遍历每一个数字。首先，1 到 n-1 中该位上为 1 的数字（使用&运算法结果大于 1 的数字）数目是确定的，其次，如果在遍历 nums[0]到 nums[n-1]，发现该位为 1 的数字的数目更多，那就说明重复的数字中该位为 1，则加到 result 中去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int result=0;
        for(int i=0;i<32;++i){
            int flag=1<<i;
            int t1=0,t2=0;
            for(int j=0;j<nums.size();++j){
                if((j&flag)>0) ++t1;
                if((nums[j]&flag)>0) ++t2;
            }
            if(t2>t1) result+=flag;
        }
        return result;
    }
};