day1 数组 removeDup & searchIn

- todo

1. Remove Duplicates from Sorted Array

    int removeDuplicates(vector<int>& nums) {
        if (nums.size()<2) return nums.size();
        int last = nums[0], writei=1;
        for (int readi=1; readi<nums.size(); ++readi) {
            if (nums[readi] != last) {
                nums[writei++] = nums[readi];
                last = nums[readi];
            }
        }
        return writei;
    }

-- 形成习惯的模式，writei总是落笔在下一个要写的地方
-- 看到第二种写法， 简单但更慢：

    int removeDuplicates(vector<int>& nums) {
        return distance( nums.begin(), unique(nums.begin(), nums.end()) );
    } ```
unique returns end() of the modified array ，新array是consecutive duplicates被处理去除后得到。

** 2] [Remove Duplicates from Sorted Array II](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/) **
```c++     
    int removeDuplicates(vector<int>& nums) {
        if (nums.size()<3) return nums.size();
        int writei = 2;
        for (int readi=2; readi<nums.size(); ++readi) {
            if (nums[readi] != nums[writei-2]) {
                nums[writei++] = nums[readi];
            }
        }
        return writei;
    }

-- 考虑overwrite原始array的情况，应该是if (nums[readi] != nums[writei-2])，和落笔前两个比而不是readi-2

3] Search in Rotated Sorted Array*

    int search(vector<int>& nums, int target) {
        int start = 0, end = nums.size()-1;
        while (start < end) {
            int mid = start + (end-start)/2; // prevent overflow
            if (nums[mid]==target) return mid;
            // lhs NON-DECENDING
            if (nums[start] <= nums[mid])
                if (nums[start]<=target && target<nums[mid]) end = mid-1;
                else start = mid+1;
            // rhs increasing 
            else 
               if (nums[mid]<target && target<=nums[end]) start = mid+1;
               else end = mid-1;
        }
        return start==end && nums[start]==target? start : -1;
    }

瞬间accept la~

- method 2 using INF

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        while (left<right) {
            int mid = left + (right-left)/2;
            if (nums[mid]==target) return mid;
            // determine "nums[mid]" in our fake acending array
            int number = nums[mid]>=nums[0] == target>=nums[0]?
                         nums[mid] :
                         target>=nums[0]? INT_MAX : INT_MIN;
            if (number < target) left = mid+1;
            else right = mid-1;
        }
        return left==right && nums[left]==target? left : -1;
    }

** 4] Search in Rotated Sorted Array II **

    bool search(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        while (left<right) {
            int mid = left + (right-left)/2;
            if (nums[mid]==target) return true;
            if (nums[left]<nums[mid])
                if (nums[left]<=target && target <nums[mid]) right = mid-1;
                else left = mid + 1;
            else if (nums[left]==nums[mid])
                ++left;
            else 
                if (nums[mid]<target && target<=nums[right]) left = mid+1;
                else right = mid-1;
        }
        return left==right && nums[left]==target;
    }    
    ```
其实就是允许重复之后，会有【1,1,2,1】这种情况出现。nums[mid] < nums[right]不能用来决定RHS是不是递增。那么分两种情况： *nums[mid] < nums[right]一定是递增；nums[mid] <== nums[right]就--right看下一步。*这道题主要是考虑什么时候特殊情况出现. 不要忘了return时的check