LeetCode-080-删除有序数组中的重复项 II

删除有序数组中的重复项 II

题目描述：给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：数组遍历

• 首先，如果数组的长度不大于2，则不可能出现元素出现超过两次的情况，直接返回；
• 如果数组的长度超过2，声明一个List为twiceNums用来记录出现过2次的数字，声明一个Set为onceNums用来记录出现过1次的数字，并且将数字的第一个数字放入onceNums中，result为数字的长度，然后遍历数组nums，从第2个元素开始遍历，遍历过程如下：
  • 如果twiceNums已经存在当前的数，说明已经出现过2次，将当前的数挪到result的位置，然后将result减一，然后进行下一轮处理；
  • 如果onceNums中存在当前的数，则将当前的数添加到twiceNums中，继续处理下一个数；
  • 如果onceNums中不存在当前的数，则将当前的数添加到onceNums中，继续处理下一个数。
• 最后返回result即为数组的新长度。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LeetCode_080 {
    public static int removeDuplicates(int[] nums) {
        // 如果数组的长度不大于2，则不可能出现元素出现超过两次的情况，直接返回
        if (nums.length == 1 || nums.length == 2) {
            return nums.length;
        }
        // 已经出现过2次的数字
        List<Integer> twiceNums = new ArrayList<>();
        Set<Integer> onceNums = new HashSet<>();
        onceNums.add(nums[0]);
        int result = nums.length;
        for (int i = 1; i < result; ) {
            if (twiceNums.contains(nums[i])) {
                // 出现过2次的，直接移到最后一位非2次的位置
                for (int j = i + 1; j < result; j++) {
                    swap(nums, j - 1, j);
                }
                result--;
                continue;
            }
            if (onceNums.contains(nums[i])) {
                // 出现过一次的，添加到twiceNums中
                twiceNums.add(nums[i]);
            } else {
                // 第一次出现的，添加到onceNums中
                onceNums.add(nums[i]);
            }
            i++;
        }
        return result;
    }

    public static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0, 0, 1, 1, 1, 1, 2, 3, 3};
        System.out.println(removeDuplicates(nums));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

【每日寄语】 一个人有了自尊心，他才可以明确地去“领导”自己向准确的途径迈进。所以，人应当一直地保持自己的尊严。