9
\$\begingroup\$

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;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I'm confused, you say unsorted, but you're using quicksort before even running the duplicate logic. \$\endgroup\$
    – Legato
    Jul 5, 2015 at 17:45
  • \$\begingroup\$ @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. \$\endgroup\$ Jul 5, 2015 at 18:17

2 Answers 2

5
\$\begingroup\$

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);

Reduce allocations

Note that removeDuplicates allocates an array to collect the unique elements (uniqueArray), and finally returns a clone of that array, with the appropriate size, thus allocating for one more array. If you don't mind modifying the input array, then you can avoid the allocation of uniqueArray by overwriting the content of the input array:

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()));
}
\$\endgroup\$
4
  • \$\begingroup\$ Your Doing it in-place source code doesn't work for all cases of unsorted array. Refer : stackoverflow.com/a/33335283/2818583 \$\endgroup\$
    – AnV
    Jul 30, 2018 at 20:13
  • \$\begingroup\$ @AnV Of course not. I think you missed some context here. This method requires that the input array is already sorted. And that is how it's used in the context of this question. Do let me know if I'm missing something. \$\endgroup\$
    – janos
    Jul 31, 2018 at 5:40
  • \$\begingroup\$ But the question says "program to remove the duplicates from an unsorted array." \$\endgroup\$
    – AnV
    Jul 31, 2018 at 5:59
  • 1
    \$\begingroup\$ @AnV yes and part of that "program to remove the duplicates from an unsorted array." in the question first sorts it. \$\endgroup\$
    – Theoriok
    Jul 31, 2018 at 6:01
4
\$\begingroup\$

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));
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Actually my though was not to use any java collection API's. \$\endgroup\$ Jul 5, 2015 at 18:24
  • 1
    \$\begingroup\$ @here4learn: No problem. You haven't explicitly mentioned it in your question so I gave it as an alternative solution. \$\endgroup\$ Jul 5, 2015 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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