题目描述（中等难度）

26 题的升级版，给定一个数组，每个数字只允许出现 2 次，将满足条件的数字全部移到前边，并且返回有多少数字。例如 [ 1, 1, 1, 2, 2, 3, 4, 4, 4, 4 ]，要变为 [ 1, 1, 2, 2, 3, 4, 4 …] 剩余部分的数字不要求。

解法一 快慢指针

利用26 题的思想，慢指针指向满足条件的数字的末尾，快指针遍历原数组。并且用一个变量记录当前末尾数字出现了几次，防止超过两次。 1. public int removeDuplicates(int[] nums) { 2. int slow = 0; 3. int fast = 1; 4. int count = 1; 5. int max = 2; 6. for (; fast < nums.length; fast++) { 7. //当前遍历的数字和慢指针末尾数字不同，就加到慢指针的末尾 8. if (nums[fast] != nums[slow]) { 9. slow++; 10. nums[slow] = nums[fast]; 11. count = 1; //当前数字置为 1 个 12. //和末尾数字相同，考虑当前数字的个数，小于 2 的话，就加到慢指针的末尾 13. } else { 14. if (count < max) { 15. slow++; 16. nums[slow] = nums[fast]; 17. count++; //当前数字加 1 18. } 19. } 20. } 21. return slow + 1; 22. }

时间复杂度：O（n）。 空间复杂度：O（1）。

解法二

参考这里，解法一中，我们用一个变量 count 记录了末尾数字出现了几次。而由于给定的数组是有序的，我们可以更直接。将当前快指针遍历的数字和慢指针指向的数字的前一个数字比较（也就是满足条件的倒数第 2 个数），如果相等，因为有序，所有倒数第 1 个数字和倒数第 2 个数字都等于当前数字，再添加就超过 2 个了，所有不添加，如果不相等，那么就添加。s 代表 slow，f 代表 fast。 1. //相等的情况 2. 1 1 1 1 1 2 2 3 3. ^ ^ 4. s f 5. //不相等的情况
6. 1 1 1 1 1 2 2 3 7. ^ ^ 8. s f

  1. public int removeDuplicates2(int[] nums) {
    2.     int slow = 1;
    3.     int fast = 2;
    4.     int max = 2;
    5.     for (; fast < nums.length; fast++) {
    6.         //不相等的话就添加
    7.         if (nums[fast] != nums[slow - max + 1]) {
    8.             slow++;
    9.             nums[slow] = nums[fast];
    10.         }
    11.     }
    12.     return slow + 1;
    13. }

时间复杂度：O（n）。 空间复杂度：O（1）。

总

快慢指针是个好东西，解法二直接利用有序，和倒数第 n 个比，从而保证末尾的数字不超过 n 个，太强了。 添加好友一起进步~ 如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^ 如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情