时间戳

首页 > 解决方案 > 从排序数组中删除重复项，以便允许两个重复项

java - 从排序数组中删除重复项，以便允许两个重复项

问题描述

问题：给定一个排序数组 nums，就地删除重复项，使重复项最多出现两次并返回新长度。

不要为另一个数组分配额外的空间，您必须通过使用 O(1) 额外内存就地修改输入数组来做到这一点。

我的解决方案：无论如何，这个代码总是在一个索引上丢失。有人可以帮我为什么吗？例如，我的示例输入应该返回 6，但它返回 5。

int[] arr2= {1,1,1,2,3,4,4};
        int i=findDupsMedium(arr2);
        System.out.println(i);


static int findDupsMedium(int[] arr) {
    int index=0;
    if(arr.length>1) {
        for(int i=0;i<2;i++) {
            arr[index++]=arr[i];

        }
    }

    //System.out.println("index:" + index);
    for(int ii=2;ii<arr.length;ii++ ) {
        int diff=ii-2;
        if(arr[ii] != arr[diff]) {

            arr[index++]=arr[ii];

        }
    }




    return index;

}

标签： java

解决方案

为此，您需要跟踪length数组的变化以及何时更新主循环的index.

boolean标志还用于跟踪一系列重复发生的时间。

   public static int findDupsMedium(int[] arr2) {
      int size = arr2.length;

      boolean foundFirstDuplicate = false;

      for (int i = 0; i < arr2.length - 1; i++) {
         for (int k = i + 1; k < size;) {
            if (arr2[i] == arr2[k]) {
               if (foundFirstDuplicate) {
                  // If we're here, this must be third
                  // duplicate in a row so copy up the array
                  // overwriting the third dupe.
                  for (int g = k; g < arr2.length - 1; g++) {
                     arr2[g] = arr2[g + 1];
                  }
                  i--; // and readjust outer loop to stay in
                       // position
                  // and effective size of array is one smaller
                  // so adjust that
                  size--;
               }
               // set first time a duplicate is found and keep this set
               // until no more duplicates
               foundFirstDuplicate = true;
               break;
            }
            // no third or more duplicate so set to false
            foundFirstDuplicate = false;
            break;
         }
      }
      return size;
   }

要验证它是否正常，请添加以下方法

     static void display(int[] a, int size) {
         int[] t = Arrays.copyOf(a, size);
         System.out.println(Arrays.toString(t));
     }

并调用方法如下：

      int[] arr2 = { 1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5
      };
      int size = findDupsMedium(arr2);
      display(arr2, size);

推荐阅读