LeetCode:Remove Duplicates from Sorted Array

开始尝试刷LeetCode提升下算法功力,打算所有算法先自己尝试编写,再参考Frank Dai(SoulMachine)在GitHub上的题解
Remove Duplicates from Sorted Array:
关键点:数组已排序,不分配另一个数组,返回去重后数组长度,每个元素只出现一次。


我的解法:
算法主要思路为不断前向查找,当找到一个不再重复的元素时,将该元素复制到已经去重的最后一个元素的下一个相邻位置。前向查找及元素复制位置由索引frontback维护。

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // 边界测试
        if (0 == n)
            return 0;

        // front 指向当前需要判断是否需要被去重的元素
        // back 指向当前已去重的最后一个元素
        int front = 1;
        int back = 0;
        // 只有一个元素时不进入循环
        for ( ; front < n; ++front) {
            if (A[front] != A[back]) {
                A[++back] = A[front];
            }
        }
        return back+1;
    }
};

参考解法1:
算法与我的算法基本相同,仅变量的定义有区别。

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if (0 == n) return 0;

        int index = 0;
        for (int i = 1; i < n; i++) {
            if (A[index] != A[i])
                A[++index] = A[i];
        }
        return index + 1;
    }
};

参考解法2:
算法主要使用STL中的unique去除相邻的重复元素,然后使用STL中的distance获取非重复元素的数目。

// 使用STL,时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        return distance(A, unique(A, A + n));
    }
};

LeetCode:Remove Duplicates from Sorted Array》上有1条评论

  1. Pingback引用通告: Remove Duplicates from Sorted Array II | 张学程

发表评论

电子邮件地址不会被公开。