Removing duplicates from an array (without sets or sorting)

Question

I have the following code:

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

        int[] unique = new int[arr.length];    //initialize new array that will hold unique values
        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++) {
                System.out.println(unique[i]);
        }
    }
}

The problem with this code (aside from being horribly slow for large arrays, but that's not the point) is that since the undeclared elements for the unique array will be set to 0, the duplicate elements from the first array are being set to 0 in unique[] (if that makes any sense). I understand why this happens, but cannot find an efficient way to fix this. I tried setting the duplicate elements to Integer.MIN_VALUE in the unique array and then printing only the elements of unique[] which are not equal to Integer.MIN_VALUE, but that seems like a weak solution to the problem. How can I fix this problem?

EDIT: If I run the code:

How many numbers are you going to enter? 4
1
2
2
0

Output:

1
0
2
0

Since the second element of the array is a duplicate, I do not set unique[1] to any value, making it default to 0. How do I avoid printing that 0, since it is not part of the original array?

EDIT 2: Yes, this is homework, but the reason I don't want to use sets, sorting, etc. is primarily that I am not familiar with them. Also, as I am not asking anyone to write the entire program for me, I think it's fine to ask for a little help.

Solution 1

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.

Solution 2

Any value that you choose (zero, min-int, max-int) to represent a removed duplicate is a problem. The user could always enter that number, and your program wouldn't behave correctly. (The only way you could legitimately use (say) min-int or max-int would be if the requirements clearly said that that number was invalid input.)

The correct way to deal with duplicates is to keep a counter of the number of non-duplicates, and make sure that the duplicates (or slots that would contain them) are at the high end of the array; i.e. indexes >= the counter. (That becomes an invariant that your algorithm needs to maintain ...)

The best solution is to eliminate the duplicates before you add them to the array. Keep a count of the number of non-duplicates and iterate until that reaches your num ... rather than the length of the array.

But if you do want to add all values to the array and then eliminate the duplicates, when you find a duplicate you need to swap elements so that you can maintain the invariant. The logic is a little bit fiddly ... but quite doable.

UPDATE

I just noticed that your original solution was using two arrays. I assumed that you were using one array, and doing an in-place update to eliminate the duplicates.

Solution 3

The best way to do this is to use a Map.

public interface Map<K,V>

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

I don't know why you would not want to use a set unless you are doing homework...

---

If you really can't use a set. Go ahead and create an ArrayList. Store the elements of the array inside, but everytime you want to store you check if the element is already part of the ArrayList.

 int [] list = {5, 5, 3, 2, 5, 3, 5};

 ArrayList<Integer> list2 = new ArrayList<Integer>();

 for(int i = 0; i < list.length; i++)
    if(!list2.contains(list[i]))
        list2.add(list[i]);

You can, if you want, turn your ArrayList back into an array.

Object[] list3 = list2.toArray();

Solution 4

You can store the maximum value entered by user (while the user is entering the values in the first loop) and then make the default value for unique equals to max + 1.

Or you can try another approach for solving the problem, something like this:

  int num = scan.nextInt();
  int[] arr = new int[num];
  int[] uniq = new int[num+1000000];
  int j = 0;

  // enter numbers into array
  for (int i = 0; i < arr.length; i++) { 
     int input = scan.nextInt(); 
     if(uniq[input] != 1){
         uniq[input] = 1;  
         arr[j] = input;
         j++;
      }
   } 

   for (int i = 0; i < j; i++) {
      System.out.println(arr[i]);
   }

Note that this solution is under the assumption that the user will not enter a number greater than (num + 1,000,000).

Solution 5

This solution allows you to enter any integer value even negative. It's your same code with some modifications and has added a parallel array for comparisons. It has also removed some lines of code that are no longer needed.

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
    int[] arrflag = new int[num];
    for (int i = 0; i < arr.length; i++) { // enter numbers into array
        System.out.print("Enter number: ");
        arr[i] = scan.nextInt();
        arrflag[i] = 0;
    }

    int[] unique = new int[arr.length];    //initialize new array that will hold unique values
    int n=0;
    for (int i = 0; i < arr.length; i++) {            
        if (arrflag[i] == 0) {
            unique[n++] = arr[i];
            for (int j = i+1; j < arr.length; j++) {    //check all elements above int i
                if (arr[i] == arr[j]) {                        
                    arrflag[j]=-1;
                }
            }                
        }
    }   
    for (int i = 0; i < n; i++) {
            System.out.println(unique[i]);
    }
}

View more solutions