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

У меня есть массив, который я заполняю 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, я не могу воспроизвести результат. Что происходит не так?


java arrays random duplicate-removal
person Arcadian    schedule 21.01.2012    source источник
comment
у него есть потенциал зацикливаться бесконечно, что, вероятно, не то, что вам нужно, см. мой ответ о том, как их избежать.   -  person soulcheck    schedule 21.01.2012
comment
да, часть, которую предложили люди, часть j < i, которая может зацикливаться, потому что и i, и j начинаются с 0, поэтому j не меньше, чем i.   -  person Arcadian    schedule 21.01.2012
comment
Это не то. Насколько я вижу, все другие решения сначала используют отрисовку, тестируют, повторяют отрисовку на той же технике диапазона. Это приводит к бесконечному циклу - диапазон рисования не становится меньше. Вы всегда можете иметь неудачу и рисовать одно и то же число до бесконечности.   -  person soulcheck    schedule 21.01.2012

Ответы (4)


arrow_upward
2
arrow_downward

На самом деле, поскольку ваш домен ограничен целыми числами от 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;
    }
}

изменить

У этого все еще есть потенциальный бесконечный цикл.

Вы вытягиваете 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);
}

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

person soulcheck    schedule 21.01.2012

arrow_upward
5
arrow_downward

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

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

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

person Baldrick    schedule 21.01.2012

arrow_upward
4
arrow_downward

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

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

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

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

должно быть

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

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

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

person NPE    schedule 21.01.2012
comment
Отредактировано, чтобы отразить первое предложение. Спасибо за это, я забыл, насколько это неэффективно. - person Arcadian; 21.01.2012
comment
Да, но я не показываю здесь весь класс. Вам нужно все это? выложу если поможет - person Arcadian; 21.01.2012
comment
@Arcadian, на самом деле это не имеет значения: это метод public, что означает, что его может вызывать кто угодно и когда угодно. Например, его можно вызвать два раза подряд. Так что не имеет значения, очищает ли массив какой-то другой код за нас или нет: массив нужно считать произвольным, никаких предположений делать не следует. - person alf; 21.01.2012

arrow_upward
1
arrow_downward

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

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);
}
person Dale K    schedule 21.01.2012
comment
Хорошо, я слежу за тем, что вы здесь делаете, используя логический флаг. Но предположим, что флаг ложный, это будет означать, что число не будет добавлено в массив, но из-за того, что цикл for имеет i++, не будет ли это означать, что он все равно перейдет к следующему элементу массива? - person Arcadian; 21.01.2012
comment
Пробовал это, кажется, все еще бесконечный цикл. Я считаю, что это из-за j < i. I начинается с 0, но j также начинается с 0. Поэтому, когда дело доходит до проверки, j не меньше, чем i. - person Arcadian; 21.01.2012
comment
Это очень странно, так как у меня он отлично работает, я поместил его в тестовый скрипт, который печатает правильные числа, а также печатает дубликаты, и это сработало. Но в любом случае не беспокойтесь, так как решение @soulcheck намного лучше. - person Dale K; 22.01.2012