关于java:LeetCode080删除有序数组中的重复项-II

10次阅读

共计 1525 个字符，预计需要花费 4 分钟才能阅读完成。

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

不要应用额定的数组空间，你必须在原地批改输出数组并在应用 O(1) 额定空间的条件下实现。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：数组遍历

首先，如果数组的长度不大于 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));
    }
}