fill an array in Java of size n with unique random numbers with complexity O(n)

Question

I have to write code to fill an array of size n with unique random numbers in the range 0-10n (inclusive). I can do it with O(n^2) complexity but I need to do it with O(n) complexity. I can't think of a way to do it that doesn't involve generating the random number, then going back through the partly filled array to check whether there are duplicates in the array.

For reference, here's my O(n^2) version of the method:

private static void fillWithUniqueN2(int[] numbers) 
{
    Random rng = new Random();
    for (int i = 0; i < numbers.length; i++)
    {
        boolean added = false;
        while (!added)
        {
            int newNumber = rng.nextInt(numbers.length);
            boolean unique = true;

            for (int j = 0; j < i; j++)
            {
                if (newNumber == numbers[j])
                {
                    unique = false;
                }
            }

            if (unique)
            {
                numbers[i] = newNumber;
                added = true;
            }   
        }       
    }
}

You can just fill the array with the values 1-n, then shuffle the array. — Bill the Lizard, Feb 27 '17 at 19:57
Do you have space complexity requirements? Can space be O(N)? If yes, you can use an O(N) shuffle. — marisbest2, Feb 27 '17 at 19:58
also see here: http://stackoverflow.com/questions/196017/unique-non-repeating-random-numbers-in-o1 (note this is not an identical question because this question is java-specific — marisbest2, Feb 27 '17 at 19:58
The values in the array have to be in the range 0-10*n. I could fill the array as Bill recommends and then multiply everything by 10 but then the answer wouldn't be truly random. — fifthfiend, Feb 27 '17 at 20:00
I guess I could initially create an array of size 10n, shuffle that, and then pick the first n values for the array that I return, that could work. — fifthfiend, Feb 27 '17 at 20:02

score 2 · Accepted Answer · answered Feb 27 '17 at 19:59

The standard solution for generating unique random numbers within a range is to:

Generate a list of all the numbers within the range - O(n)
Shuffle the list - O(n)
Extract the first N items from the list - O(1) or O(n)

Therefore the entire operation would be O(n).

Eric Duminil · Answer 2 · 2017-02-27T20:24:24.877

To shuffle the entire list in O(n), you could use Fisher-Yates shuffle :

-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
     j ← random integer such that i ≤ j < n
     exchange a[i] and a[j]

As a bonus, it's already implemented in Collections.shuffle() (the doc mentions it runs in linear time).

package stackOverflow;

import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;


public class FisherYates
{
    public static void main(String[] args) {
        int n = 10;
        IntStream range = IntStream.rangeClosed(0, n * 10);
        List<Integer> integers = range.boxed().collect(Collectors.toList());
        Collections.shuffle(integers);
        System.out.println(integers.subList(0, n));
    }
}

As an example, it outputs :

[28, 44, 26, 94, 21, 65, 55, 25, 99, 93]
[40, 57, 3, 42, 61, 26, 64, 45, 19, 41]
...

score -3 · Answer 3 · answered Feb 27 '17 at 19:56

-3

Keep a Set of entries already entered. For each candidate check whether the Set already contains the entry. If not, add it to the array and to the Set (assuming your check didn't simultaneously add to the Set), otherwise generate a new candidate. Repeat for each candidate until you succeed, then proceed to the next open slot in the array.

answered Feb 27 '17 at 19:56

Lew Bloch

3,364
1
16
10

1

this isnt guaranteed to stop, let alone O(N). – marisbest2 Feb 27 '17 at 19:57
Is there any algorithm that's guaranteed to stop? The random sequence could generate the same number forever with any algorithm. However, we don't have a random sequence. We have a pseudorandom sequence. Probabilistically the complexity approaches O(N). The only way to guarantee a stop with any algorithm is to limit the number of retries. I'm open; if you have a better solution, publish it. – Lew Bloch Feb 27 '17 at 20:04
1

Since the range is bounded, he can generate each number in the range exactly once. Then shuffle. Or he can use a modular sequence that is guaranteed not to repeat. – marisbest2 Feb 27 '17 at 20:05
Is shuffling O(N)? – Lew Bloch Feb 27 '17 at 22:16

fill an array in Java of size n with unique random numbers with complexity O(n)

3 Answers3