Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Remove Duplicates from Sorted Array

Leetcode algorithms 第 26 题:Remove Duplicates from Sorted Array。

题目

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

解答

移除已排序数组中的重复元素,使用指针记录当前新数组的末尾位置。如果当前遍历的元素不等于该末尾位置的元素,则为新元素,插入到末尾,否则直接丢弃,处理下一个元素。

具体代码如下:

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if (n == 0) return 0;
        
        int last = 0;
        for (int i = 1; i < n; i++)
            if (A[i] != A[last]) //新元素
                A[++last] = A[i];//插入到末尾
        return last + 1;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论