Identifying duplicates before adding them into an array

Question

I am attempting to write a program, that consists of an array, filled with 50 random numbers, between the values 1-999. However before a random number is added to the array, I must check that the number is not a duplicate and not already in the array.

I seem to be fairly close to the correct output, however for some reason, i repeatedly get the number 0 as the first element in my array, and it is also the only number that is ever duplicated. Does anyone know why this is, and if so be able to provide a suitable fix?

Once a duplicate is found, it needs to be printed to the output, and replaced by a new unique random number.

Thanks in advance.

import java.util.*;
public class Random50 {
public static void main (String[] args)
{
    final int MAX_SIZE = 50;
    int[] r50 = new int[MAX_SIZE];
    boolean duplicates = false;

    Random rand = new Random();

    for (int i=0; i<r50.length; i++)
    {   
        for (int j=i+1;j<r50.length;j++)
        {
            r50[i] = rand.nextInt(1000);

            if (j!=i && r50[i] == r50[j])
            {
                duplicates = true;
                System.out.println("DUPE: " + r50[i]);
                r50[i] = rand.nextInt(1000);
            }

        }
    }

    System.out.println(Arrays.toString(r50));
}

}

You aren't unsetting duplicates after you find a duplicate — Kevin L
– Kevin L, Commented Aug 18, 2014 at 13:44
Any reason you can't use a collection? Collection objects have a .contains() method. — Patrick J Abare II
– Patrick J Abare II, Commented Aug 18, 2014 at 13:45
You might want to use a Set<Integer> if you need to keep non-duplicate items. Your code could then be quite simple - loop, adding values to your set until it has 50 elements. — Duncan Jones
– Duncan Jones, Commented Aug 18, 2014 at 13:46
Following the advices for Set might be the best choice but to comment on your code after if (j!=i && r50[i] == r50[j]) is not guaranteed to get a non-duplicate number. Use a while for this. — Eypros
– Eypros, Commented Aug 18, 2014 at 13:55

Sherz · Accepted Answer · 2014-08-18 14:11:03Z

j is always greater than i, because you initialize j as i+1. That means that the values of r50 that are referenced by j are always 0, so those will always be the duplicates.

For example, if i = 20, in the second loop, j will start at 21. r50[21], r50[22], etc... are all 0, because you haven't set them yet, so the only possible duplicate of r50[i] and r50[j] is 0.

Edit: If the point of j is to iterate through all the previous elements of the array, then you'll want

   for (int i=0; i<r50.length; i++)
    {   
        r50[i] = rand.nextInt(1000); //Set it before the j loop
        for (int j = 0; j < i; j++)
        {
            while (r50[i] == r50[j]) //while loop, in case of multiple duplicates
            {
                duplicates = true;  //Still not sure why you want this boolean
                System.out.println("DUPE: " + r50[i]);
                r50[i] = rand.nextInt(1000);
            }
    }
}

Though this still won't work perfectly, because you might set r50 to an earlier value, after you checked it. For example, if you made sure that r50[20] isn't equal to any values of j through 10, and then it is equal to r50[11] (when j = 11), then you might accidentally change it back to a value of j less than that (for example, r50[5]).

I think the neatest way is, as Duncan and Rajeev have,

HashSet numbers = new HashSet();
Random rand = new Random();

while(numbers.size() < MAX_SIZE) {
    numbers.add(rand.nextInt(1000));
}

I see what you mean, I hadn't thought of that! Does this mean I should initialise j equal to i then?
I'm not sure what the point of j is, to be honest. Are you trying to check that no other value was added beforehand? In that case, you want j to start at 0, but to go up to i. But the neatest answer is Rajeev's, with my edit.

Kumar Abhinav · Accepted Answer · 2014-08-18 14:06:49Z

Performance wise,this isnt a good way as every time you are comparing a value with the next positions of the array.You should use the hashing algorithm whereby you can know at which point an Object may lie depending on its unique hashcode and here comes into the picture HashSet which has O(1) for most operations and this is very less chance of hashcode collision in Integer class Objects

public static void main (String[] args)
{
    final int MAX_SIZE = 50;

    HashSet<Integer> hs = new HashSet<Integer>(50);

     while(hs.size()<50){

        Random rand = new Random();
        int randomVal = rand.nextInt(1000);
        hs.add(randomVal);
    }
   Integer[] r50 = hs.toArray();
}

Collectives™ on Stack Overflow

Identifying duplicates before adding them into an array

2 Answers 2

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Related