Removing duplicates from a Array [duplicate]

Question

I am dealing with the following problem from my data structure book. I have come up with the solution as suggested by this text . I basically found all the duplicates and labelled them some arbitrary number like 666 and then removed them from the array.

My question to everyone is - is my solution is exactly as the text suggested? - also what is a more effective method to solve this problem?

Here is the complete code (LOOK at the nodups method to see my solution)

public 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 void noDups() {
        int i = 0;
        long compareKey;

        while (i < nElems) {

            compareKey = a[i];

            for (int j = 0; j < nElems; j++) {
                if (j != i && a[j] != 666) {
                    if (a[j] == compareKey) {
                        a[j] = 666;
                    }
                }
                j++;
            }

            i++;
        }

        for (int k = 0; k < nElems; k++) {
            if (a[k] == 666) {
                delete(a[k]);
            }
        }

    }

    public boolean delete(long value) {

        int j;
        for (j = 0; j < nElems; j++)
            if (a[j] == value)
                break;

        if (j == nElems) {
            return false;
        }

        else {
            for (int k = j; k < nElems - 1; k++)
                a[k] = a[k + 1];
            nElems--;
            return true;
        }
    }

    public long removeMax() {

        if (nElems != 0) {
            long maxValue = a[0];

            for (int i = 0; i < nElems; i++) {
                if (a[i] > maxValue)
                    maxValue = a[i];
            }

            delete(maxValue);
            return maxValue;
        }

        else {
            return -1;
        }
    }

    public void display() {

        for (int i = 0; i < nElems; i++) {
            System.out.println(a[i]);
        }
    }

}

The following class has main method.

public class HighArrayApp {

    public static void main(String[] args) {

        HighArray arr = new HighArray(100);

        arr.insert(2);
        arr.insert(2);
        arr.insert(3);
        arr.insert(4);
        arr.insert(4);
        arr.insert(5);

        arr.display();

        arr.noDups();

        System.out.println("-------------------------");

        arr.display();

    }

}

I highly appreciate any suggestions and i am open to all kinds of approaches that attempt a more effective algorithm for this problem.

Answer 1

You solution is valid but as you said, I think there is a more efficient approach. I also think the given text implies this ("One approach is ...", "Another approach is...").

Comparing each element with the others is O(n^2).

If you sort the array first, you can remove duplicates with a single walk through the array.

Sorting is O(n log n), walking through is O(n).

The total complexity is then O( n log n) + O(n) = O(n log n).

This solution is valid, as the text clearly states that the order of the objects may be changed.