Reputation: 9348

Avoiding duplicate integers in an integer array

How can duplicate integers being added into an integer array be avoided without using any of the collections i.e. Arraylist or Set etc.?

Upvotes: 1

Answers (7)

Dhwaneet Bhatt

Reputation: 611

The solution depends on your requirement. If you have a small array size (n<10^6), scanning through the array on every insertion would suffice, but if you have a large array and frequent insertions, I would propose a different solution.

Scanning through an array on every insertion would require a complexity of O(n). For small numbers, the overhead is ignorable, but as the size of array increases, traversal on every insertion is inefficient.

If you need performance and if memory is not your constraint, you can take a boolean array and initialize all elements to false. Then whenever you get a number, make its index value in the boolean array to true, And while inserting, check whether the boolean value at the index number of the element being inserted.

Here is the code to initialize the boolean array (initializing it would make all elements false):

boolean [] duplicateValuesArray = new boolean[Integer.MAX_VALUE];

Here is the function which inserts an element in the array:

    public void insertElement(int elementToBeInserted) {
        if(!duplicateValuesArray[elementToBeInserted])  //check if element already in array
            duplicateValuesArray[elementToBeInserted] = true;
            mainArray[index++] = elementToBeInserted;
    }

In this way, whenever you get a number, value for that index in the boolean array is set to true, and while insertion, everytime the index is checked, if value is true, that element exists in the array, do not insert it.

The complexity for this is much lower if you have a large mainArray (n>10^6) and you have frequent insertions. This is because, initializing a boolean array is one time O(n) complexity, and after that, checking for the element in the boolean array and insertion of element is just O(1) operation, happens in constant time.

Thus effective complexity is reduced to just initializing the boolean array. And even in terms of memory footprint, I wouldn't mind because a boolean primitive just occupies one bit in the memory.

P.S: Basically it is a memory vs performance trade off, and this is the Universal Computing Trade off, found everywhere.

Upvotes: 2

Priyank Doshi

Reputation: 13151

I would suggest first you perform Arrays.Sort( int[] ). Then use Arrays.binarySearch( int [] ,int ) to check whether the element exist or not.

According to javadoc:

/**
 * Sorts the specified array of ints into ascending numerical order.
 * The sorting algorithm is a tuned quicksort, adapted from Jon
 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
 * 1993).  This algorithm offers n*log(n) performance on many data sets
 * that cause other quicksorts to degrade to quadratic performance.
 *
 * @param a the array to be sorted
 */
public static void sort(int[] a) {
sort1(a, 0, a.length);
}

and for BinarySearch:

 /**
 * Searches the specified array of ints for the specified value using the
 * binary search algorithm.  The array must be sorted (as
 * by the {@link #sort(int[])} method) prior to making this call.  If it
 * is not sorted, the results are undefined.  If the array contains
 * multiple elements with the specified value, there is no guarantee which
 * one will be found.
 *
 * @param a the array to be searched
 * @param key the value to be searched for
 * @return index of the search key, if it is contained in the array;
 *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
 *         <i>insertion point</i> is defined as the point at which the
 *         key would be inserted into the array: the index of the first
 *         element greater than the key, or <tt>a.length</tt> if all
 *         elements in the array are less than the specified key.  Note
 *         that this guarantees that the return value will be &gt;= 0 if
 *         and only if the key is found.
 */
public static int binarySearch(int[] a, int key) {
return binarySearch0(a, 0, a.length, key);
}

And one you know whether the element exist or not, rest is easy for you.

Upvotes: 1

M The Developer

Reputation: 59

First Assuming the Array is a buffer and has extra Space.

Simply loop through it checking each value. Such As

    for(int i=0;  i<endpointer  &&i < buffer.length  ; i++){
        if(buffer[i]==valueToPutInArray){
            valueExists=true;
            break;
        }
    }
    if(!valueExists)    {
        buffer[endpointer++]=valueToPutInArray;

    }

If the Array is must be reallocated then you have to do something like this:

    int i=0;
    Integer[] outputArray = new Integer[buffer.length+1];
    for(Integer value : buffer) {
        if(value==valueToPutInArray){
            valueExists=true;
            break;
        }
        outputArray[i++]=value;
    }
    if(!valueExists)    {
        outputArray[i]=valueToPutInArray;

    }

Upvotes: 0

davioooh

Reputation: 24676

If your problem is to return an Integer[], and not any other collection, you could however use a Set<Integer> privately to avoid duplicated values, and then return Set<Integer>.toArray(new Integer[0]).

That's the simplest way IMHO...

For example:

private Set<Integer> intSet = new HashSet<Integer>();

public void setIntArray(Integer[] i){
    intSet = new HashSet<Integer>(Arrays.asList(i));
}

public Integer[] getIntArray(){
    return intSet.toArray(new Integer[0]);
}

Upvotes: 1

user845279

Reputation: 2804

You can create another array, let's call it exists, of type boolean. Then each time you add an integer to your main list check if exists[newNumber]. If the value is true it already exists, otherwise add the number to the integer array and set the boolean value to true.

This solution works well if the number range has a small bound. Note, my example also assumes the integer is positive. Some optimization is to use a long[] array and use each bit as a flag.

Upvotes: 1