Removing duplicates from an array

Question

I am dealing with the following problem from my book on data structure. I came up with the solution suggested in this text. I basically found all the duplicates and designated them as an arbitrary number, like 666, and then removed them from the array.

My question for everyone is my decision exactly as suggested in the text? - is also a more effective method of solving this problem?

Here is the complete code (VIEW 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 a 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 appreciate any suggestions, and I am open to all kinds of approaches that try to use a more efficient algorithm for this problem.

Answer 1

, , , , . , ( " ...", " - ..." ).

O(n^2).

, .

O(n log n), O(n).

O( n log n) + O(n) = O(n log n).

, , .

Answer 2

, Lambda Expression

:

public class LambdaTest     
{
    public static void main (String[] args)
    {

         List<Integer> objList = Arrays.asList(1,1,2,3,2,4,5,2,5);
         objList .forEach(i -> System.out.print(" " + i));
         System.out.println();
         List<Integer> noDub =objList.stream().distinct().collect(Collectors.toList());
         noDub.forEach(i -> System.out.print(" " + i));
    } 
}

:

1 1 2 3 2 4 5 2 5 

1 2 3 4 5

Answer 3

. HashSet?

import java.util.*;

public class Test
{
    public static void main(String[]args)
    {
        Integer [] arr = new Integer[]{4, 3, 1, 2, 4, 3, 2};
        Set<Integer> hs = new HashSet<Integer>(Arrays.asList(arr));
        System.out.println(hs);
    }
}

Answer 4

, , , , .

-, , 666 , , , .

-, HighArray , . ArrayList , .

HighArray, a HashSet, . HashSet .

Set<Long> uniqueNumbers = new HashSet<Long>(Arrays.asList(a));
a = uniqueNumbers.toArray(new long[uniqueNumbers.size()]);

- O(n lg(n)) O(n), , O(n^2) .

Answer 5

The algorithm described in the book is akin to bubble sorting. The easiest way is to use two nested loops.

for (int i=0; i < a.length;i++) {
    long ref = a[i];
    for (int j=i+1; j < a.length; j++) {
        if(a[j] == ref) {
            a[j] = Long.MIN_VALUE;
        }
    }
}

I forgot the cleaning part.