Duplicates in a sorted java array

Question

I have to write a method that takes an array of ints that is already sorted in numerical order then remove all the duplicate numbers and return an array of just the numbers that have no duplicates. That array must then be printed out so I can't have any null pointer exceptions. The method has to be in O(n) time, can't use vectors or hashes. This is what I have so far but it only has the first couple numbers in order without duplicates and then just puts the duplicates in the back of the array. I can't create a temporary array because it gives me null pointer exceptions.

public static int[] noDups(int[] myArray) {
    int j = 0;
    for (int i = 1; i < myArray.length; i++) {
        if (myArray[i] != myArray[j]) {
            j++;
            myArray[j] = myArray[i];
        }
    }
    return myArray;
}

You can't convine the two operations, sort and remove duplicates? I think that's the better solution. — 4gus71n, Oct 18 '13 at 04:09
@astinx - well, he's getting the array pre-sorted, so combining the operations isn't necessary. Note that most 'good' sorts are considered to run in O(n log n) time, which exceeds O(n) time, so that wouldn't help him anyways. Note that, while a combined search/remove operation is likely to be faster, doing so interferes with _composability_, the ability for larger functions to be made from smaller ones (ie, the normal course is to have a sort function, and a remove-sorted-duplicates function, and combine those). — Clockwork-Muse, Oct 18 '13 at 07:11
Could you read my answer? I edited t will solve your problem. Also, try to comment on answers and give feedback. — Michael Yaworski, Oct 18 '13 at 19:20

score 4 · Accepted Answer · answered Oct 18 '13 at 04:07

4

Since this seems to be homework I don't want to give you the exact code, but here's what to do:

Do a first run through of the array to see how many duplicates there are
Create a new array of size (oldSize - duplicates)
Do another run through of the array to put the unique values in the new array

Since the array is sorted, you can just check if array[n] == array[n+1]. If not, then it isn't a duplicate. Be careful about your array bounds when checking n+1.

edit: because this involves two run throughs it will run in O(2n) -> O(n) time.

answered Oct 18 '13 at 04:07

telkins

10,440
8
52
79

Thank you so much, I found this comment to be the most helpful. I really needed help understanding the assignment and not just the code itself. – Max Frazier Oct 24 '13 at 23:32
@MaxFrazier No problem, sometimes that's all it takes. If it answered your question please mark my answer as accepted. :) – telkins Oct 25 '13 at 02:18

Michael Yaworski · Answer 2 · 2013-10-18T04:54:51.113

Tested and works (assuming the array is ordered already)

public static int[] noDups(int[] myArray) { 

    int dups = 0; // represents number of duplicate numbers

    for (int i = 1; i < myArray.length; i++) 
    {
        // if number in array after current number in array is the same
        if (myArray[i] == myArray[i - 1])
            dups++; // add one to number of duplicates
    }

    // create return array (with no duplicates) 
    // and subtract the number of duplicates from the original size (no NPEs)
    int[] returnArray = new int[myArray.length - dups];

    returnArray[0] = myArray[0]; // set the first positions equal to each other
                                 // because it's not iterated over in the loop

    int count = 1; // element count for the return array

    for (int i = 1; i < myArray.length; i++)
    {
        // if current number in original array is not the same as the one before
        if (myArray[i] != myArray[i-1]) 
        {
           returnArray[count] = myArray[i]; // add the number to the return array
           count++; // continue to next element in the return array
        }
    }

    return returnArray; // return the ordered, unique array
}

My previous answer to this problem with used an Integer List.

@astinx `The method has to be in O(n) time, can't use vectors or hashes.` — Michael Yaworski, Oct 18 '13 at 04:29

score 0 · Answer 3 · answered Oct 18 '13 at 04:15

Not creating a new array will surely result in nulls all over the initial array. Therefore create a new array for storing the unique values from the initial array.

How do you check for unique values? Here's the pseudo code

uniq = null
loop(1..arraysize)      
  if (array[current] == uniq)  skip
  else  store array[current] in next free index of new array; uniq = array[current]
end loop

Also as others mentioned get the array size by initial scan of array

uniq = null
count = 0
loop(1..arraysize)      
  if (array[current] == uniq)  skip
  else  uniq = array[current] and count++
end loop
create new array of size count

score 0 · Answer 4 · answered Oct 18 '13 at 04:19

public static int[] findDups(int[] myArray) {
    int numOfDups = 0;
    for (int i = 0; i < myArray.length-1; i++) {
        if (myArray[i] == myArray[i+1]) {
            numOfDups++;
        }
    }
    int[] noDupArray = new int[myArray.length-numOfDups];
    int last = 0;
    int x = 0;
    for (int i = 0; i < myArray.length; i++) {
        if(last!=myArray[i]) {
            last = myArray[i];
            noDupArray[x++] = last;
        }
    }
    return noDupArray;
}

score 0 · Answer 5 · answered Oct 18 '13 at 06:11

public int[] noDups(int[] arr){

    int j = 0;
    // copy the items without the dups to res
    int[] res = new int[arr.length];
    for(int i=0; i<arr.length-2; i++){
        if(arr[i] != arr[i+1]){
            res[j] = arr[i];
            j++;
        }
    }
    // copy the last element
    res[j]=arr[arr.length-1];
    j++;
    // now move the result into a compact array (exact size)
    int[] ans = new int[j];
    for(int i=0; i<j; i++){
        ans[i] = res[i];
    }
    return ans;
}

First loop is O(n) and so is the second loop - which totals in O(n) as requested.

Duplicates in a sorted java array

5 Answers5

Linked