26. Remove Duplicates from Sorted Array

O(n) time

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for x in nums:
            if nums[i] != x:
                i += 1
                nums[i] = x
        return i + 1

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (empty(nums)) return 0;
        int i = 0;
        for (int x : nums) {
            if (nums[i] != x) {
                nums[++i] = x;
            }
        }
        return i + 1;
    }
};

用这个

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for x in nums:
            if i < 1 or nums[i - 1] < x:
                nums[i] = x
                i += 1
        return i

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0;
        for (int x : nums) {
            if (i < 1 || x > nums[i - 1]) {
                nums[i++] = x;
            }
        }
        return i;
    }
};

快慢指针解法O(n)
题解
快指针fast遍历整个数组，遇到和slow不相同的数，就把nums[fast]赋给slow的下一个，同时慢指针slow向前一步

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        int last = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[last] != nums[i]) {
                nums[++last] = nums[i]; // 先加加再写就可以了
            }
        }
        return last + 1; // 因为last是下标，所以要返回last + 1才是个数
    }
};

朴素解法O(n)
在每个位置从当前位置开始向后找到第一个比当前位置之前一个数更大的数赋给当前位置，每次向后找的时候就从之前找到的那个更大的数的位置继续向后找即可

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        int i = 1, j = i;
        for (; i < n; ++i) {
            if (nums[i] <= nums[i - 1]) {
                do { ++j; } while (j < n && nums[j] <= nums[i - 1]);
                if (j < n) nums[i] = nums[j];
                else return i;
            }
        }
        return n;
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        for (int i = 1, j = i; i < n; ++i) {
            for (; j < n; ++j) {
                if (nums[j] > nums[i - 1]) {
                    nums[i] = nums[j];
                    break;
                }
            }
            if (j == n) return i;
        }
        return n;
    }
};