首页 > ACM题库 > LeetCode > LeetCode-Remove Duplicates from Sorted Array II[数组]
2014
11-18

LeetCode-Remove Duplicates from Sorted Array II[数组]

Remove Duplicates from Sorted Array II

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

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

标签: Array Two Pointers
分析

加一个变量记录一下元素出现的次数即可。这题因为是已经排序的数组,所以一个变量即可解决。如果是没有排序的数组,则需要引入一个hashmap来记录出现次数。

代码1

// LeetCode, Remove Duplicates from Sorted Array II
// 时间复杂度O(n),空间复杂度O(1)
// @author hex108 (https://github.com/hex108)
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

// LeetCode, Remove Duplicates from Sorted Array II
// @author 虞航仲 (http://weibo.com/u/1666779725)
// 时间复杂度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;
    }
};

Java代码:

public class Solution {
    public static int removeDuplicates(int[] A) {
        if(A.length <= 2) return A.length;
        int dup = 1;
        int index = 1;
        for(int i=1; i<A.length; i++){
            if(A[i] == A[i-1])
                dup++;
            else
                dup = 1;
            A[index] = A[i];
            if(dup <= 2){
                index++;
            }
        }
        return index;
    }
}

相关题目
Remove Duplicates from Sorted Array


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。