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

Question

问题:给定一个排序数组 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;

}

Answer 1

你的方法没问题，但缺少某些部分。

这是一个有点脏的解决方案，它适用于连续的重复项。

如果输入数组在不同位置有重复项，则必须实现另一个 for 循环。

static int findDupsMedium(int[] arr) {

    int count=0;

    //used for extracting duplicates from the length of array
    int extract=0;  

    if(arr.length>1) {

        // this is for having a comparison withot getting outOfBounds;
        int lastItem=0;      

        for(int i=0; i<arr.length; i++) {

            //If we had 2 duplicates and new one is the same with previous one, remove 
            if(count == 2 && lastItem == arr[i]){

                //if end of the array has duplicate, make it "-1"
                if(i==arr.length-1){
                    arr[i]=-1;
                }
                else{
                    extract++;  //we found a duplicate

                    lastItem = arr[i];

                    //shift it
                    for(int j=i;j<arr.length-1;j++){
                        arr[j]=arr[j+1];
                    }
                }
                //printArray(arr);                    

                count = 0;
            }
            else{

                if(arr[i+1]==arr[i]){
                    count++;
                    lastItem = arr[i];
                }
            }
        }
    }

    return arr.length - extract;
}