This is the 23rd day of my participation in the August More Text Challenge.More challenges in August

Delete duplicate item II from an ordered array

Give you an ordered array nums, please delete the repeated elements in place, so that each element appears at most twice, return the new length of the array after deletion.

Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: array traversal
  • First, if the length of the array is not greater than 2, it is impossible for the element to appear more than twice.
  • If the array length is greater than 2, declare a List as twiceNums to record the number that has occurred twice, declare a Set as onceNums to record the number that has occurred once, and place the first number of the number into onceNums. Result is the length of the number, then loop through nums. Starting with the second element, the loop is traversed as follows:
    • If the current number of twiceNums already exists, it has already occurred twice. Move the current number to result, and then subtract result by one.
    • If the current number exists in the onceNums, the current number is added to the twiceNums and the next number is processed.
    • If the current number does not exist in the onceNums, the current number is added to the onceNums and the next number is processed.
  • Return result as the new length of the array.
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) {
        If the array length is not greater than 2, the element cannot be present more than twice
        if (nums.length == 1 || nums.length == 2) {
            return nums.length;
        }
        // The number that has already appeared twice
        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])) {
                // If it occurs twice, move to the last non-twice position
                for (int j = i + 1; j < result; j++) {
                    swap(nums, j - 1, j);
                }
                result--;
                continue;
            }
            if (onceNums.contains(nums[i])) {
                // If it occurs once, add it to twiceNums
                twiceNums.add(nums[i]);
            } else {
                // Add the first occurrence to 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)); }}Copy the code

When a person has self-esteem, he can definitely “lead” himself to the right path. Therefore, people should always keep their dignity.