287. Find the Duplicate Number

發表於 | 分類於

problem

給定一維陣列，找出重複一遍的數字，其餘數字皆為不重複。不能修改原陣列。

solution

  • set stl
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            unordered_set<int> s;
            for(int n:nums){
                if(s.count(n)) return n;
                s.insert(n);
            }
            return -1;
            
           
        }
    };
  • modify value
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            int n = nums.size();
            for(int i=0;i<n;++i){
                int idx = abs(nums[i])-1;
                // number has visited/ modified
                if(nums[idx]<0) return idx+1;
                else nums[idx] *=-1;
            }
            return -1;   
        }
    };
  • sorting
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            for(int i=1;i<nums.size();++i){
                if(nums[i] == nums[i-1]) return nums[i];
            }
            return -1;
        }
    };

    option 1 - Two Pointers

  • 利用兩個索引，一個跑的慢，一個跑得快，並找出相交位置。找到後一個從原點開始再跑，另一個從相遇地點開始跑。在遇到則為答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        //  1   3   4   2   2   
        
        //slow 0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4
        //fast 0 -> 3 -> 4 -> 4 -> 4
        
        //slow 4 -> 2 -> 4 -> 2 
        //fast 0 -> 1 -> 3 -> 2 
        int slow =0, fast = 0;
        while(1){
            slow = nums[slow];
            fast = nums[nums[fast]];
            if(slow==fast) break;
        }
        slow = 0;
        while(1){
            slow = nums[slow];
            fast = nums[fast];
            if(slow==fast) return slow;
        }
        return -1;   
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)