Leetcode026

LeetCode026：删除排序数组中的重复项        给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

解法一：基于C++双标记方法

       我们使用两个标记i,j,其中i标记第一个元素下标，j也从第一个下标开始for循环，
如果nums[i]小于nums[j],修改i的下一个元素nums[++i]=nums[j];直到最后for循环完毕
注意：题目说了你不需要考虑数组中超出新长度后面的元素。

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        int len = nums.size();
        if (len == 0) 
            return 0; //所给数组为空
        int i = 0, j = 0;
        for (j = 0; j<int(nums.size());)
        {
            if (nums[i] < nums[j])
            {
                nums[++i] = nums[j];

            }
            j++;
        }
        return i + 1;
    }
};

解法二：基于C++双指针

       首先题目要求常数级别的空间复杂度，这个时候首先想到指针，使用双指针法可以解决这个问题。
由于数组是有序的，所以我们用两个指针，第一个指针指向第一个元素，第二个指针指向第二个元素。用第二个指针遍历数组，如果发现第二个指针指向元素的值大于第一个指针指向元素，这个时候将第一个指针向后移动一个元素，然后修改第一个指针指向的元素，直到for循环完成。

class Solution2 {
public:
    int removeDuplicates(vector<int>& nums)
    {
        //先处理特殊情况，否则会产生执行错误
        if (nums.size() == 0)  //所给数组为空
            return 0;
        auto itr1{ nums.begin() };  //指针1指向第一个元素
        auto itr2{ nums.begin() + 1 };  //指针2指向第二个元素
        for (itr2; itr2 != nums.end(); ++itr2)  //遍历数组
        {
            if (*itr2 > * itr1)  //发现和指针1不相同的数
            {
                itr1 += 1;  //指针1向后移动一个元素
                *itr1 = *itr2;  //修改指针1的值
            }
        }
        return itr1 - nums.begin() + 1;  //返回数组长度
    }
};

解法三：基于C++单标记单指针：(提倡，用时最少，内存消耗最少，也好理解)

       遍历nums中的元素n，与指针对应的元素进行比较，如果不同，则替换初始指针后面的位置为新的元素n

class Solution3 {
public:
    int removeDuplicates(vector<int>& nums) {

        if (nums.size() == 0)    return 0;

        int i = 0;   //i做标记，记录需要替换元素的位置 
        /**********************************************************
        基于for的范围语句
        通过auto关键字让编译器来决定变量n的类型，这里n是int类型，
        每次迭代，nums的下一个数字被拷贝给n，因此该循环可以理解为
        “对于数组nums中的每个数字，执行循环体内的操作。”
        *********************************************************/
        for (auto n : nums) 
        {
            if (n != nums[i])
                nums[++i] = n;
        }

        return i + 1;
    }
};

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    //vector<int> nums{ 1,1,2 };
    //vector<int> nums{ 0, 0, 1, 1, 1, 2, 2, 3, 3, 4 };
    vector<int> nums;
    int Size;
    cout << "请输入数组的大小 Size：" << endl;
    cin >> Size;
    int currval;
    cout << "请输入数组元素：" << endl;
    for (int m = 0; m < Size; m++)
    {
        cin >> currval;
        nums.push_back(currval);
    }

    Solution3 answer;
    cout << "The length of nums is: " << answer.removeDuplicates(nums) << endl;

    system("pause");
    return 0;
}