10.LeetCode 80:Remove Duplicates from Sorted Array II

迈不过友情╰ 2022-03-02 04:56 149阅读 0赞

1.题目

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NsNzIzNDAx_size_16_color_FFFFFF_t_70][]

2.解决

package com.cl.ch2;
    
    import java.util.Arrays;
    
    public class RemoveDuplicatesTwice {
    
        /**
         * 时间复杂度O(n)
         * 空间复杂度O(1)
         * @param nums
         * @return
         */
        public int removeDuplicates(int[] nums) {
            //数组空
            if(nums.length<=0){
                return 0;
            }
            //[0,k]是符合条件的序列，
            //count:temp重复的次数记录
            // temp存储当前进入[0,k]的元素
            int k=0,count=1,temp=nums[k];
           for(int i=1;i<nums.length;i++){
               if(nums[i]==temp){
                   //重复个数<2，第i个元素应该进入[0,k]的有效序列中
                   //超过3个重复不符合条件，k不能增加
                   if(count<2) {
                       //如果不是相邻的两个元素重复（发生过交换），
                       // 将第i个元素放入k+1的位置
                       if(i-k!=1){
                           swap(nums,k+1,i);
                       }
                       //直接把第i个元素融入[0,k]
                       k++;
                   }
                   //只要重复的就count++
                   count++;
               }else{
                   //遇到新的的元素，与k+1的元素交换
                   swap(nums,++k,i);
                   //当前进入[0,k]的元素记录为temp，重复出现次数为1
                   temp=nums[k];
                   count=1;
    
               }
           }
            return k+1;
        }
    
    
        private void swap(int[] nums, int k, int i) {
            int tem = nums[k];
            nums[k]=nums[i];
            nums[i]=tem;
        }
    
        public static void main(String[] args) {
            int[] arr = new int[]{0,0,1,1,1,1,2,3,3};
            System.out.println(new RemoveDuplicatesTwice().removeDuplicates(arr));
            System.out.println(Arrays.toString(arr));
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NsNzIzNDAx_size_16_color_FFFFFF_t_70]: /images/20220302/ff1daed8533a41fbb1b689465a4bdc35.png