第287题---Find the Duplicate Number

• 题意描述

  • 给定一个包含n+1个数的数组，其中数的范围为[1, n]之间，至少存在一个重复的数，找出这个重复的数

• 思路1

  • 暴力破解（N的平方）

• 思路2（限制，数组为n+1,如果小于n+1就不可行了，可能a[n]不存在的情况，和数组必定存在重复数的前提）

  • 类似于找到环的起点的解法，一个走一步，一个走两步，因为存在重复的数，必定可以相遇，然后再fast指针起点，开始移动

    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            int size = nums.size();
            if(size == 0)
                return 0;
                
            int low = nums[0];
            int fast = nums[low];
            
            while(low != fast) {
                low = nums[low];
                fast = nums[nums[fast]];
            }
            
            fast = 0;
            while (low != fast) {
                low = nums[low];
                fast = nums[fast];
            }
            return fast;
        }
    };

• 思路3 令牌桶算法（毛？）

  class Solution {
  public:
      int findDuplicate(vector<int>& nums) {
          int index = 0;
          while(index < nums.size()) {
              if(nums[index] == index) {
                  index ++;
              } else {
                  if(nums[index] == nums[nums[index]])
                      return nums[index];
                  else {
                      int temp = nums[index];
                      nums[index] = nums[temp];
                      nums[temp] = temp;
                  }
              }
          }
          return -1;
      }
  };