java - noDups()方法从数组中删除所有重复项

Question

它会删除数组中的重复项，但会跳过末尾附近的一项。有人能帮我解决这个问题吗？

输出如下:

77 44 55 33 55 22 88 11 33 66 33 

正在删除重复项...

77 44 55 22 88 11 33 

它在应该打印时跳过了'66'。

这是我的代码: HighArray.java

class HighArray {
private long[] a;
private int nElems;

public HighArray(int max) {
    a = new long[max];
    nElems = 0;
}

public boolean find(long searchKey) {
    int j;
    for(j=0; j<nElems; j++)
        if(a[j] == searchKey)
            break;
    if(j == nElems)
        return false;
    else
        return true;
}

public void insert(long value) {
    a[nElems] = value;
    nElems++;
}

public boolean delete(long value) {
    int j;
    for(j=0; j<nElems; j++)
        if( value == a[j] )
            break;
    if(j==nElems)
        return false;
    else {
        for(int k=j; k<nElems; k++)
            a[k] = a[k+1];
        nElems--; 
        return true;
    }
}

public void noDups() {
    System.out.println("\nRemoving duplicates...");

    for(int i = 0; i<nElems; i++) {
        for(int j = i+1; j<nElems; j++) {
            if (a[i] == a[j]) {
                delete(a[i]);
                nElems--;
            }
        }
    }
    //return duplicates;
}

public void display(){
    for(int j=0; j<nElems; j++)
        System.out.print(a[j] + " ");
    System.out.println("");
}

}

HighArrayApp.java

class HighArrayApp {

public static void main(String[] args) {

    int maxSize = 100;
    HighArray arr;
    arr = new HighArray(maxSize);

    arr.insert(77);
    arr.insert(55);
    arr.insert(99);
    arr.insert(44);
    arr.insert(55);
    arr.insert(33);
    arr.insert(55);
    arr.insert(22);
    arr.insert(88);
    arr.insert(11);
    arr.insert(33);
    arr.insert(00);
    arr.insert(66);
    arr.insert(33);

    arr.display();

    int searchKey = 35;
    if( arr.find(searchKey) )
        System.out.println("Found " + searchKey);
    else
        System.out.println("Can’t find " + searchKey);

    arr.delete(00);
    arr.delete(55);
    arr.delete(99);

    arr.display();

    arr.noDups();
    arr.display();
}

}

Answer 1

在迭代数组时不应修改索引，否则您会看到一些奇怪的结果。迭代肯定会跳过一些元素，因为它们的索引不是应该的索引。

假设您像这样迭代数组:

0 1 2 3 4 5  // indices
1 2 5 6 7 8  // array elements
^
i            // current position of i

现在删除索引 0 处的元素。然后所有剩余的元素都会向左移动，但 i 将继续向前移动。删除索引0处的元素后，数组结构如下:

0 1 2 3 4   // indices
2 5 6 7 8   // array elements
  ^
  i         // current position of i (Will move from 0 to 1)

看，下一个处理的元素将是 5，而不是 2。这就是您的代码跳过元素的原因。

<小时/>

您可以通过向后迭代数组来解决此问题，这不会修改要处理的剩余元素的索引。哦，你不需要嵌套 for 循环。只需单个 for 循环即可完成任务。

修改你的循环:

for(int i = nElems; i > 0; i--) {
        if (a[i] == a[i + 1]) {
            delete(a[i]);
         // nElems--; // Not needed here. (You're already doing this in delete())
        }
    }

话虽如此，请考虑使用 Set 来完成此任务。这就是 Java API 中存在 Set 的原因。它会自动删除重复的元素。