How to Efficiently Remove Duplicates from an Array Without Using Set

How to efficiently remove duplicates from an array without using Set

Since this question is still getting a lot of attention, I decided to answer it by copying this answer from Code Review.SE:

You're following the same philosophy as the bubble sort, which is
very, very, very slow. Have you tried this?:

• Sort your unordered array with quicksort. Quicksort is much faster
  than bubble sort (I know, you are not sorting, but the algorithm you
  follow is almost the same as bubble sort to traverse the array).

• Then start removing duplicates (repeated values will be next to each
  other). In a for loop you could have two indices: source and
  destination. (On each loop you copy source to destination unless they
  are the same, and increment both by 1). Every time you find a
  duplicate you increment source (and don't perform the copy).
  @morgano

How to efficiently remove duplicates from an array without using Set

Since this question is still getting a lot of attention, I decided to answer it by copying this answer from Code Review.SE:

You're following the same philosophy as the bubble sort, which is
very, very, very slow. Have you tried this?:

• Sort your unordered array with quicksort. Quicksort is much faster
  than bubble sort (I know, you are not sorting, but the algorithm you
  follow is almost the same as bubble sort to traverse the array).

• Then start removing duplicates (repeated values will be next to each
  other). In a for loop you could have two indices: source and
  destination. (On each loop you copy source to destination unless they
  are the same, and increment both by 1). Every time you find a
  duplicate you increment source (and don't perform the copy).
  @morgano

How can I remove duplicates from array without using another array?

If you really want this in constant space, you need to be careful not to do anything that will reallocate a new array or a temp array. You can do this by simply overwriting the elements at the front of the array and keeping track of the count. At the end, the solution will be the front slice of the array from 0 to count:

a = [0,0,1,1,1,2,2,3,4]

current = None
count = 0

for n in a:
    if n != current:
        a[count] = n
        count+=1
        current = n

a[:count]  
# [0, 1, 2, 3, 4]

This will be linear time and constant space.

Removing the duplicates from an array without disturbing the order of elements without using Sets

You can do it in O(n^2) time with O(1) extra space.

public static int[] noSpaceElementDistinctness(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n;i++) {
        boolean exists = false;
        for (int j = 0; j < i; j++) {
            if (arr[i] == arr[j]) {
                exists = true;
                break;
            }
        }
        if (exists) {
            for (int j = i+1; j<n; j++)
                arr[j-1] = arr[j];
        n--;
        i--; //to iterate the next element, which is now at index i, not i+1.
        }
    }
    for (int i = n; i < arr.length; i++) arr[i] = Integer.MIN_VALUE; //indicates no value
    return arr;

}

---

As a side note, the element distinctness problem is not that trivial to solve efficiently as it might seem from first glance, and it is one problem with strict lower bound of what you can do to solve it efficiently. This thread discusses it.

Removing duplicates from an array (without sets or sorting)

I am going to use the tools that you used to solve the problem, cuz something in me is telling me this is homework...

import java.util.Scanner;

public class ArrayDuplicates 
{

   public static void main(String[] args) 
   {

      Scanner scan = new Scanner(System.in);

      System.out.print("How many numbers are you going to enter? ");
      int num = scan.nextInt();

      int[] arr = new int[num]; // initialize array with user inputted length

      for (int i = 0; i < arr.length; i++)// enter numbers into array
      {

         arr[i] = scan.nextInt();

      }

      double[] unique = new double[arr.length];    //initialize new array that will hold unique values

      ///////My edit

      for(int z = 0; z < unique.length; z++)
      {

         unique[z] = -0.5;

      }

      ///////

      for (int i = 0; i < arr.length; i++) 
      {

         boolean b = true;    //boolean that checks if an element is a duplicate

         for (int j = i+1; j < arr.length; j++)    //check all elements above int i
         {

            if (arr[i] == arr[j]) 
            {

               b = false;    // set b to false if there is an existing duplicate

            }

         }

         if (b) 
         {

            unique[i] = arr[i];    // if no duplicates exist, then it is unique.

         }

      }   

      for (int i = 0; i < unique.length; i++) 
      {

         if(!(unique[i] == -0.5))
         {

            System.out.println((int)(unique[i]));

         }

      }

   }
}

So, you see where I commented out my edit? that's the new thing, a very easy way to check is to give the values a number that is not expected, in this case, a negative number. Now, that is an assumption on my part, change -1 to whatever value you know will not be entered into that Scanner. Same for the if statement.

---

Related Topics