Проверьте наличие дубликатов при заполнении массива

Question

У меня есть массив, который я заполняю 6 случайно сгенерированными числами.Сначала он генерирует случайное число от 1 до 49, а затем сравнивает его с числами в массиве.Если он находит дубликат, он должен снова сгенерировать случайное число, а затем выполнить проверку еще раз.Если дубликатов нет, число добавляется в массив.

Вот код:

public void populateArray()
{
    for(int i = 0; i < numberLine.length; i++)
    {
        randomNumber = 1 + randomGen.nextInt(49);
        for(int j = 0; j < i; j++)
        {
            if (numberLine[j] == randomNumber)
            {
                i--;
            }
            else
            {
                continue;
            }
        }
        if(i >= 0)
        {
            numberLine[i] = randomNumber;
        }
        else
        {
            continue;
        }
    }
    Arrays.sort(numberLine);
}

Однако по какой-то причине это по-прежнему допускает дублирование, хотя и редко (около 1в 50 массивах), например 6 6 16 24 34 46.Но когда я пытаюсь продублировать это, выбрав элемент случайного числа и используя число, подобное 30, я не могу воспроизвести результат.Что не так?

Answer 1

С коллекциями было бы намного проще, например, TreeSet, который отсортирован и без дубликатов

Set<Integer> set = new TreeSet<Integer>();
while (set.length() < 6) {
    set.add(randomGen.nextInt(49));
} 

Используйте toArray() после этого, если вы действительно хотите иметь массив.

Answer 2

Вот что может случиться. Допустим, вы уже нарисовали 1 и 2. На третьей итерации вы снова рисуете 1. Что происходит, так это то, что ваш внутренний цикл будет уменьшаться i один раз , после чего numberLine[i] = randomNumber поместит 1 в секунду . Теперь у вас есть 1, 1 в вашем массиве. QED.

Разобравшись с багом, у меня есть пара предложений:

1) Следующее:

for(int j = 0; j < numberLine.length; j++)

должно быть

for(int j = 0; j < i; j++)

В противном случае вы смотрите на позиции, которые еще не заполнены.

2) Я бы переписал весь алгоритм, используя SortedSet: просто продолжайте добавлять случайные числа в набор, пока он не достигнет желаемого размера. В конце используйте toArray(). Это автоматически позаботится о дедупликации и сортировке и будет иметь более сложную временную сложность, чем ваше текущее решение.

Answer 3

На самом деле, поскольку ваш домен ограничен целыми числами от 1 до 49, лучше использовать массив логических значений, чтобы указать, было ли уже нарисовано число:

public void populateArray()
{
    count = 0;
    boolean[] used = new boolean[50];
    while (count < 6) {
        randomNumber = 1 + randomGen.nextInt(49);
        if (!used[randomNumber]) ++count;
        used[randomNumber] = true;
    }


    int j = 0;
    for (int i = 1; i < used.length; ++i) {
        numberLine[j++] = i;
    }
}

edit

Это все еще имеет потенциальный бесконечный цикл.

Вы рисуете 6 чисел из 49 без дубликатов.Правильное решение будет таким:

 public void populateArray() {
    List<Integer> pool = new ArrayList<Integer>();
    for (int i = 0; i < 49; ++i) {
        pool.add(i + 1);
    }

    for (int i = 0; i < 6; ++i) {
        randomNumber = randomGen.nextInt(pool.size());
        numberLine[i] = pool.get(randomNumber);
        pool.remove(randomNumber);
    }

    Arrays.sort(numberLine);
}

Конечные циклы, такое же распределение вероятностей, как и у исходного.Вместо повторного рисования при обнаружении дубликата, вы просто исключаете возможность рисования дубликата заранее.По сути, он подражает настоящей лотерее.

Answer 4

Все остальные предложения одинаково хороши, вот код, который, я думаю, должен работать:

public void populateArray()
{
    boolean OK = true;
    int i = 0;
    while (i < numberLine.length)
    {
        randomNumber = 1 + randomGen.nextInt(49);
        for(int j = 0; j < i; j++) if (numberLine[j] == randomNumber) OK = false;
        if (OK)
        {
            numberLine[i] = randomNumber;
            i++;
        }
        OK = true;
    }
    Arrays.sort(numberLine);
}