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\$
  • 1
    \$\begingroup\$ I'm confused, you say unsorted, but you're using quicksort before even running the duplicate logic. \$\endgroup\$ – Legato Jul 5 '15 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\$ – here4learn Jul 5 '15 at 18:17
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\$
  • \$\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 '18 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 '18 at 5:40
  • \$\begingroup\$ But the question says "program to remove the duplicates from an unsorted array." \$\endgroup\$ – AnV Jul 31 '18 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 '18 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\$
  • 1
    \$\begingroup\$ Actually my though was not to use any java collection API's. \$\endgroup\$ – here4learn Jul 5 '15 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\$ – barak manos Jul 5 '15 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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