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

雪柳花明 2016-10-06

展开全文

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

01// LeetCode, Remove Duplicates from Sorted Array II
02// 时间复杂度O(n)，空间复杂度O(1)
03// @author hex108 (https://github.com/hex108)
04class Solution {
05public:
06    int removeDuplicates(int A[], int n) {
07        if (n <= 2) return n;
08 
09        int index = 2;
10        for (int i = 2; i < n; i++){
11            if (A[i] != A[index - 2])
12                A[index++] = A[i];
13        }
14 
15        return index;
16    }
17};

代码2

01// LeetCode, Remove Duplicates from Sorted Array II
02// @author 虞航仲 (http://weibo.com/u/1666779725)
03// 时间复杂度O(n)，空间复杂度O(1)
04class Solution {
05public:
06    int removeDuplicates(int A[], int n) {
07        int index = 0;
08        for (int i = 0; i < n; ++i) {
09            if (i > 0 && i < n - 1 && A[i] == A[i - 1] && A[i] == A[i + 1])
10                continue;
11 
12            A[index++] = A[i];
13        }
14        return index;
15    }
16};

Java代码:

01public class Solution {
02    public static int removeDuplicates(int[] A) {
03        if(A.length <= 2) return A.length;
04        int dup = 1;
05        int index = 1;
06        for(int i=1; i<A.length; i++){
07            if(A[i] == A[i-1])
08                dup++;
09            else
10                dup = 1;
11            A[index] = A[i];
12            if(dup <= 2){
13                index++;
14            }
15        }
16        return index;
17    }
18}