如何高效生成无重复随机数填充数组？（基于Java.util.Random）

Hey there! Your current approach works, but restarting the entire comparison loop every time a duplicate is found is what's dragging down efficiency—with 225 elements, that leads to tons of redundant checks and retries. Let's fix this with a far more efficient method that avoids those pitfalls.

The Problem with Your Current Code #

Your implementation first fills the array with random numbers (which will definitely have duplicates), then scans for duplicates and regenerates values, resetting the entire loop each time. In the worst case, this could run exponentially slower as you get closer to filling the array (since the chance of picking an unused number gets smaller).

The Efficient Solution: Fisher-Yates Shuffling (In-Place) #

Instead of generating random numbers and fixing duplicates later, we can start with a fully ordered array (1 to 225) and shuffle it in place using the Fisher-Yates algorithm. This runs in O(n) time (each element is processed exactly once) and uses minimal extra space—perfect for your constraints.

How It Works: #

1. Initialize an array with numbers 1 through 225 (no duplicates by default).
2. Iterate from the last element back to the first:
   • For each index i, generate a random index j between 0 and i (inclusive).
   • Swap the elements at positions i and j.
3. By the end of the loop, the array will be randomly shuffled with no duplicates.

Code Implementation #

import java.util.Random;

public class RandomArrayGenerator {
    public static void main(String[] args) {
        int[] value = new int[225];
        Random random = new Random();

        // Step 1: Fill array with ordered numbers 1-225
        for (int i = 0; i < value.length; i++) {
            value[i] = i + 1;
        }

        // Step 2: Fisher-Yates shuffle in place
        for (int i = value.length - 1; i > 0; i--) {
            // Generate random index between 0 and i (inclusive)
            int j = random.nextInt(i + 1);
            // Swap elements at i and j
            int temp = value[i];
            value[i] = value[j];
            value[j] = temp;
        }

        // Optional: Print the array to verify
        for (int num : value) {
            System.out.print(num + " ");
        }
    }
}

Why This Is Better #

• Efficiency: No duplicate checks or retries—each element is touched exactly once. For 225 elements, this will run in a fraction of the time compared to your current approach.
• Guaranteed No Duplicates: Since we start with a unique ordered set and only swap elements, duplicates are impossible.
• Minimal Space: Uses only the original array plus a few temporary variables—no extra data structures like boolean arrays (though those are better than your current method, Fisher-Yates is still superior).

Alternative: Using a Boolean Tracking Array (If You Prefer) #

If you want to generate random numbers directly without starting from an ordered array, you can use a boolean array to track which numbers have been used. This is O(n) time too, but uses a bit more space:

import java.util.Random;

public class RandomArrayAlternative {
    public static void main(String[] args) {
        int[] value = new int[225];
        boolean[] used = new boolean[226]; // Indexes 0-225, we use 1-225
        Random random = new Random();

        int index = 0;
        while (index < value.length) {
            int randNum = random.nextInt(225) + 1;
            if (!used[randNum]) {
                value[index] = randNum;
                used[randNum] = true;
                index++;
            }
        }

        // Optional: Print the array
        for (int num : value) {
            System.out.print(num + " ");
        }
    }
}

This avoids duplicates by checking if a number has been used before adding it to the array. It's better than your original approach but slightly less efficient than Fisher-Yates since it might generate some unused random numbers (though for 225 elements, this is negligible).

内容的提问来源于stack exchange，提问作者Hasnain Ali