current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 9 down vote favorite

I have written this program to remove the duplicates from an unsorted array. Please review and give me your input on how I can improve it a little more.

public static void main(String[] args) {

    int[] arr = {4, 3, 4, 2, 6, 1, 1, 7, 6, 8, 9, 9, 1, 1};

    // perform quick sort for o(n log n) time.
    quickSort(arr, 0, arr.length - 1);

    System.out.println(Arrays.toString(arr));
    // now remove the duplicate elements.
    arr = removeDuplicates(arr);
    System.out.println("Unique elements in Array :" + Arrays.toString(arr));
}
private static int[] removeDuplicates(int[] arr) {
    // if array length is one, return the array
    if (arr.length <= 1) {
        return arr;
    }

    // new array keep the length equal to current array.
    int[] uniqueArray = new int[arr.length];
    // keep the lastfound number to be 0th index.
    int lastFound = arr[0];
    // copy the 0th index value to new arrays 0th.
    uniqueArray[0] = arr[0];

    // keep track of number of duplicates found.
    int totalDuplicates = 0;

    // current index position to put the unique number
    int currPos = 1;
    for (int i = 0; i < arr.length; i++) {

        if (lastFound == arr[i]) {
            totalDuplicates++;
        } else {
            lastFound = arr[i];
            uniqueArray[currPos] = arr[i];
            currPos++;
        }
    }

    // at this point array wil have unique numbers along with empty
    // slots at the end in array, lets remove those.

    int newLength = arr.length - totalDuplicates;

    uniqueArray = Arrays.copyOf(uniqueArray, newLength + 1);
    return uniqueArray;
}

private static void quickSort(int[] arr, int s, int e) {

    if (s < e) {
        int pivot = findPivot(arr, s, e);
        System.out.println(pivot);
        // sort left
        quickSort(arr, s, pivot - 1);
        // sort right
        quickSort(arr, pivot + 1, e);
    }

}

private static int findPivot(int[] arr, int s, int e) {
    int p = arr[e];
    int i = s;
    for (int j = s; j < e; j++) {
        if (arr[j] <= p) {
            swap(arr, i, j);
            i = i + 1;
        }
    }
    swap(arr, e, i);
    return i;
}

private static void swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}
share|improve this question
    
I'm confused, you say unsorted, but you're using quicksort before even running the duplicate logic. – Legato Jul 5 '15 at 17:45
    
@Legato Actually my input is an unsorted array, and I am using "quicksort to sort and then putting a logic to remove duplicates" as a part of whole approach to solve the problem. – here4learn Jul 5 '15 at 18:17
up vote 4 down vote accepted

Improving removeDuplicates

It's recommended to use an enhanced for-each loop instead of a counting loop when possible:

    for (int num : arr) {
        if (lastFound == num) {
            totalDuplicates++;
        } else {
            lastFound = num;
            uniqueArray[currPos] = num;
            currPos++;
        }
    }

And you can get rid of totalDuplicates, as currPos already contains that same information:

    int currPos = 1;
    for (int num : arr) {
        if (lastFound != num) {
            lastFound = num;
            uniqueArray[currPos] = num;
            currPos++;
        }
    }

    return Arrays.copyOf(uniqueArray, currPos);

I noticed later that your original code does an unnecessary comparison for the first element or arr: it would be enough to iterate from the 2nd element. Unfortunately, for that we need to bring back the counting loop:

    int currPos = 1;
    for (int i = 1; i < arr.length; ++i) {
        int num = arr[i];
        if (lastFound != num) {
            lastFound = num;
            uniqueArray[currPos] = num;
            currPos++;
        }
    }

    return Arrays.copyOf(uniqueArray, currPos);

Although I'm not really a fan of this, but for the record you could save one line by combining these two:

            uniqueArray[currPos] = num;
            currPos++;

into:

            uniqueArray[currPos++] = num;

Doing it in-place

If you don't mind modifying the input array, then you can do this in-place, without allocating extra memory for uniqueArray:

private static int[] removeDuplicates(int[] arr) {
    if (arr.length <= 1) {
        return arr;
    }

    int lastFound = arr[0];

    int currPos = 1;
    for (int i = 1; i < arr.length; ++i) {
        int num = arr[i];
        if (lastFound != num) {
            lastFound = num;
            arr[currPos++] = num;
        }
    }

    return Arrays.copyOf(arr, currPos);
}

Unit testing

To verify the implementation works, and for safe refactoring, it's good to have some unit tests around, for example:

@Test
public void test_1_2_3() {
    int[] orig = {1, 2, 3};
    assertArrayEquals(orig, removeDuplicates(orig.clone()));
}

@Test
public void test_empty() {
    int[] orig = {};
    assertArrayEquals(orig, removeDuplicates(orig.clone()));
}

@Test
public void test_single() {
    int[] orig = {3};
    assertArrayEquals(orig, removeDuplicates(orig.clone()));
}

@Test
public void test_1_1_1() {
    int[] orig = {1, 1, 1};
    assertArrayEquals(new int[]{1}, removeDuplicates(orig.clone()));
}

@Test
public void test_1_1_1_2_2_3_3_3() {
    int[] orig = {1, 1, 1, 2, 2, 3, 3, 3};
    assertArrayEquals(new int[]{1, 2, 3}, removeDuplicates(orig.clone()));
}

@Test
public void test_1_2_3_3_3() {
    int[] orig = {1, 2, 3, 3, 3};
    assertArrayEquals(new int[]{1, 2, 3}, removeDuplicates(orig.clone()));
}

@Test
public void test_1_2_2_2_3() {
    int[] orig = {1, 2, 2, 2, 3};
    assertArrayEquals(new int[]{1, 2, 3}, removeDuplicates(orig.clone()));
}
share|improve this answer
1  
Thank you!! and +1 for answering so thoroughly. – here4learn Jul 5 '15 at 21:42
up vote 3 down vote

You can simply use a HashSet instead:

int[] arr = {4, 3, 4, 2, 6, 1, 1, 7, 6, 8, 9, 9, 1, 1};
Set<Integer> set = new HashSet<Integer>();
for (int n : arr)
    set.add(n);
Integer[] arr2 = set.toArray(new Integer[set.size()]);
System.out.println("Unique elements in Array :" + Arrays.toString(arr2));
share|improve this answer
    
Actually my though was not to use any java collection API's. – here4learn Jul 5 '15 at 18:24
    
@here4learn: No problem. You haven't explicitly mentioned it in your question so I gave it as an alternative solution. – barak manos Jul 5 '15 at 18:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.