LeetCode:Remove Duplicates from Sorted Array II

接前一题(Remove Duplicates from Sorted Array),但元素最多允许出现的次数由1变为2。
LeetCode OJ地址:http://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
关键点:数组已排序,不分配另一个数组,返回去重后数组长度,每个元素最多出现两次。


我的解法1:
1.遍历数组,将其中重复次数在两次以上的所有元素进行标记(mark,此处使用A[0]-1作为mark,对于A[0]本身为最小int时可能存在问题?)。
2.从第一个重复次数在两次以上且该数第三次出现的位置开始遍历,当元素不是被标记的元素时,将该元素往前移动。
算法需要执行两次循环及一次STL的find操作,虽然时间复杂度在O(n),但实际效果并不好,且代码冗长。
对于一个测试用例,算法在执行过程中的数组状态如下代码中的高亮行所示。

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

        // 假定输入 [0,1,1,2,2,2,2,3,3,4,4,4]

        int front = 1;
        int back = 0;
        int mark = A[0]-1;  // 把比最小元素小1的元素做为[标记]
        int count = 1;      // 记录元素遇到的次数
        // 将出现次数超过两次的重复元素做标记
        for ( ; front < n; ++front) {
            if (A[front] == A[back]) {
                ++count;
                if (count > 2) {
                    A[front] = mark;
                }
            }
            else {
                // 非重复元素
                count = 1;     // 重置计数
                back = front;  // 将back直接定位到此非重复元素
            }
        }

        // 执行上述循环后数组 [0,1,1,2,2,-1,-1,3,3,4,4,-1]

        // 定位到第一个被标记的元素位置
        back = find(A, A+n, mark) - A;
        front = back+1;

        // 将非标记元素往前移
        // 不存在重复次数两次以上的元素时,不会进入此循环
        for ( ; front < n; ++front) {
            if (mark != A[front]) {
                A[back++] = A[front];
            }
        }

        // 执行上述循环后数组 [0,1,1,2,2,3,3,4,4,4,4,-1]
        return back;
    }
};

我的解法2:
1.定位到第一个第三次重复的元素。
2.遍历数组,当一个元素与已去重的最后两个元素都相同时,说明该元素是第三次或更多次出现,跳过该元素;否则将该元素复制到已去重元素的下一个位置。
算法需要执行一次循环及一次STL的find_if操作。

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeDuplicates(int A[], int n) {        
        if (n < 3)
        {
            // 已包含 n == 2
            // 后续有起始地址 A+2
            // 且元素个数不超过3个时重复元素最多个数不超过2
            return n;
        }

        // 查找第一个第三次重复元素的位置
        int *pos = find_if(A+2, A+n,
                           [&](int& i){
            // int& i  需要根据地址计算偏移,必须以引用传入
            int offset = (&i)-A;      // 偏离数组起点长
            return i == A[offset-2];  // 将传入元素与其在数组中前2个位置的元素比较
        });

        // 定位到第一个第三次重复的元素
        // find_if 返回 A+n 时不会进入下面的循环
        int back = pos-A;
        int front = back+1;
        for ( ; front < n; ++front) {
            if (A[front] == A[back-1]
                    && A[front] == A[back-2]) {
                continue;
            }
            else {
                A[back++] = A[front];
            }
        }

        return back;
    }
};

参考解法1:
算法由前一题的与最后一个已去重元素比较修改为与最后一个已去重元素的前一个元素(index-2)进行比较,确定元素重复次数是否超过两次,若未超过两次则复制该元素到已去重元素的下一个位置。
该解法去除了我的解法2中的find_if操作,直接从数组第三个元素开始判断;同时由我的解法2中的与已去重数组的最后两个元素相等比较修改为与最后一个已去重元素的前一个元素不相等比较。
算法仅需对数组做一次简单遍历,简洁清晰。

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if (n <= 2)
            return n;
        int index = 2;
        for (int i = 2; i < n; i++) {
            if (A[i] != A[index-2])
                A[index++] = A[i];
        }
        return index;
    }
};

参考解法2:
由前述解法的与已去重元素进行比较,修改为与当前遍历元素的前一个元素及后一个元素进行比较,若两次相等比较都成立,则说明该元素重复次数超过两次,跳过该元素;否则将该元素复制到已去重元素之后。
由于采用的是与当前元素的前一个元素及后一个元素进行比较,故数组第一个元素及最后一个元素直接保留。

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        int index = 0;
        for (int i = 0; i < n; ++i) {
            if (i > 0 && i < n-1
                    && A[i] == A[i-1] && A[i] == A[i+1])
                continue;
            A[index++] = A[i];
        }
        return index;
    }
};

发表评论

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