问题:给定一个已排序的数组num,就地删除重复项,以使重复项最多出现两次,并返回新的长度。
不要为另一个数组分配额外的空间,必须通过使用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;
}
最佳答案
您的方法还可以,但是缺少某些部分。
这是一个有点肮脏的解决方案,它适用于连续重复。
如果输入数组在不同位置有重复项,则必须实现另一个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;
}
关于java - 从排序数组中删除重复项,以便允许两个重复项,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/59338790/