leetcodeno.26removeduplicatesfromsortedarray(c++…

LeetCode No.26 Remove Duplicates from Sorted Array (C++实现)

LeetCode是一家国外的技术在线刷题网站，提供大量的算法题目，使得程序员能够练习算法，提高编程技能。其中，LeetCode No.26 Remove Duplicates from Sorted Array是一道非常经典的算法题目，本文将介绍该题的C++实现。

题目描述

给定一个有序数组，删除其中的重复元素，返回处理后的新数组，重复元素只保留一个，并且在原数组中的位置不能改变。

例如，num=[0,0,1,1,1,2,2,3,3,4], 在删除重复元素后，新数组应该为[0,1,2,3,4]。

解题思路

该问题可用两个指针i,j解决。指针i用来指向数组中不重复的位置，指针j扫描整个数组。当nums[i]==nums[j]时，说明有重复元素需要删除，同时指针j向后移动。当nums[i]!=nums[j]时，说明找到了一个新元素，此时指针i向后移动一个位置，并赋值为nums[j]，指针j继续向后移动，在重复以上过程，直到数组遍历结束。

C++代码如下：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0;
        //遍历数组
        for (int j = 0; j < nums.size(); j++) {
            if (j == 0 || nums[j] != nums[j - 1]) {
                nums[i++] = nums[j];
            }
        }
        return i;
    }
};

复杂度分析

• 时间复杂度：O(n)，其中n是数组的长度。因为数组中的每个元素最多遍历一次。
• 空间复杂度：O(1)，因为该方法只使用了常量级别的额外空间。

总结

本文介绍了使用指针方式，对一个有序数组进行去重处理的C++模板实现。它是一道广泛使用的面试题，在工业界的数据处理中也经常出现。掌握该算法有助于提高程序员的算法和编程能力。

以上就是本文对LeetCode No.26 Remove Duplicates from Sorted Array（C++）的介绍，希望能够对算法爱好者和程序员有所帮助。