题目大意: 给定一个有序整型数组,数组中存在重复值,允许数组中的值至多出现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; } }