Leetcode: Remove Duplicates from Sorted Array II 理解分析

时间:2021-01-08 07:37:29

题目大意: 给定一个有序整型数组,数组中存在重复值,允许数组中的值至多出现2次,将数组去重后,并返回其长度。

理解:1)与Remove Duplicates from Sorted Array(http://blog.csdn.net/blog_szhao/article/details/24301413)要求相同,本题允许元素出现两次;

2)仍然使用两个指针,一个始终指向有效数组的最后一个元素,另一个扫描数组。同时令设一个count记录相同元素在有效数组中出现的次数,最大值为2。

实现:

public class Solution {
    public int removeDuplicates(int[] A) {
        if(A == null || A.length == 0) return 0;
        int len = A.length;
        if(len == 1) return 1;
        int i = 0, j = 1; // 两个指针
        int res = 1; // 记录去重后数组的长度
        int count = 1; // 记录允许相同元素的个数,最大为2
        while(j < len) {
            if(A[j] == A[i]) {
                if(count < 2) {
                    res ++;
                    if(j > i + 1) A[i + 1] = A[j]; // 两个元素不相邻
                    i ++;
                    count ++;
                }
            }
            else {
                res ++;
                if(j > i + 1) A[i + 1] = A[j]; // 两个元素不相邻
                i ++;
                count = 1;
            }
            j ++;
        }
        return res;
    }
}