Манипуляция байтовым массивом - вопрос интервью

Question

У меня была эта дискуссия с моим другом, который задал ему этот вопрос в интервью.Вопрос идет так.Напишите функцию, которая принимает байтовый массив (двухмерный) в качестве входных данных вместе с целым числом n. Первоначальное предположение состоит в том, что все элементы байтового массива M * N равны нулю, и проблема состоит в том, чтобы заполнить элементы байтового массива n значением1, например, если M = 5 и N = 5, а значение n равно 10, массив байтов должен иметь 10/25 элементов, равных 1, а остальные 15 значений - 0. Заполненные значения должны быть случайными и иметь одну ячейку.в байтовом массиве следует заполнять только один раз.Я был очарован, пытаясь решить это самостоятельно.Я приложил код, который придумал до сих пор.

public Boolean ByteArrayFiller(int a,int b, int n)
    {
        int count = n;
        int iLocalCount = 0;
        byte[,] bArray= new byte[a,b];
        for (int i = 0; i <a; i++)
            for (int j = 1; j <b; j++)
                bArray[i, j] = 0;

        Random randa=  new Random();
        int iRandA = randa.Next(a);
        int iRandB = randa.Next(b);

        while (iLocalCount < n)
        {
            if (bArray[iRandA, iRandB] == 0)
            {
                bArray[iRandA, iRandB] = 1;
                iLocalCount++;
            }

            iRandA = randa.Next(a);
            iRandB = randa.Next(b);
            continue;
        }
        //do
        //{
        //     //iRandA = randa.Next(a);
        //     //iRandB = randa.Next(b);
        //    bArray[iRandA,iRandB]=1;
        //    iLocalCount++;

        //} while (iLocalCount<=count && bArray[iRandA,iRandB]==0);

        return true;
    }

Код, который я написал, написан на C #, но его легко понять.Он в состоянии справиться с задачей вопроса (я выполнил несколько пробных запусков, и результаты были получены правильно), но я использовал объект Random в C # (эквивалент Math.Rand в Java), чтобы заполнить массив байтов, и я продолжаю думать, еслиRand возвращает одинаковые значения для a и b.Для этого есть все шансы на неопределенный срок.Это цель вопроса?Или решение, которое я нашел для этого вопроса, достаточно хорошее!

Мне любопытно посмотреть, как эксперты здесь решают эту проблему?Я просто ищу новые идеи, чтобы расширить свой кругозор.Любые указатели будут с благодарностью.Спасибо, что нашли время, чтобы прочитать этот пост!

Answer 1

Цикл while, пробующий случайные места до тех пор, пока он не найдет хорошее, как правило, очень плохой подход.Если n = M * N, то последний будет иметь вероятность 1 / (M * N) нахождения совпадения.Если M * N достаточно велико, это может быть крайне неэффективно.

Если M * N не слишком велико, я бы создал временный массив размером M * N, заполнив его числами от 0 до (M* N) -1, а затем переставить его - т.е. вы проходите через него и меняете текущее значение на другое случайное значение.

Затем вы переходите к первым n элементам в вашем массиве и устанавливаете соответствующиеклетка.(строка = значение / столбцы, столбец = значение% столбцов).

Answer 2

Я бы логически рассматривал массив как одномерный массив.Заполните первые n позиции заданным значением, а затем перемешайте массив.

С учетом байтового массива, а также количества строк и столбцов в массиве и предполагая, что массив уже заполнен 0:

int NumElements = NumRows * NumCols;

for (int i = 0; i < NumElementsToFill; ++i)
{
    int row = i / NumRows;
    int col = i % NumCols;
    array[row, col] = 1;
}

// Now shuffle the array
Random rnd = new Random();

for (int i = 0; i < NumElements; ++i)
{
    int irow = i / NumRows;
    int icol = i % NumCols;

    int swapWith = rnd.Next(i+1);
    int swapRow = swapWith / NumRows;
    int swapCol = swapWith % NumCols;

    byte temp = array[irow, icol];
    array[irow, icol] = array[swapRow, swapCol];
    array[swapRow, swapCol] = temp;
}

Ключ здесь - преобразование одномерного индекса в значения строки / столбца.Я использовал / и %.Вы также можете использовать Math.DivRem.Или создайте Action методы, которые выполняют get и set для вас.

Answer 3

В сущности, вам нужно выбрать n уникальных случайных чисел из диапазона [0, p) (где p = M * N) и сопоставить их с позициями 2-мерного массива.

Наивные подходы: 1) генерировать неуникальные числа с повтором 2) заполнить массив числами от 0 до p-1, перемешать его и взять первые n чисел (занимает O (p) время, O (p)) памяти).

Другой подход заключается в выборе их с помощью следующего алгоритма (O (n ² ) времени, O (n) памяти, код на Java):

public Set<Integer> chooseUniqueRandomNumbers(int n, int p) {
    Set<Integer> choosen = new TreeSet<Integer>();
    Random rnd = new Random();

    for (int i = 0; i < n; i++) {
        // Generate random number from range [0, p - i)
        int c = rnd.nextInt(p - i);

        // Adjust it as it was choosen from range [0, p) excluding already choosen numbers
        Iterator<Integer> it = choosen.iterator();
        while (it.hasNext() && it.next() <= c) c++;

        choosen.add(c);
    }

    return choosen;
}

Отображение сгенерированных чисел в позиции двумерного массива тривиально.

Answer 4

Выберите число, которое больше, чем N и M, и простое (или взаимно простое для N и M). Давайте назовем этот номер p.

Цикл, пока вы не установите x числа:

1. Генерирует случайное число меньше, чем N * M. Назовите этот номер `l`.
2. Тогда следующим местом для ввода числа будет `p * l% (N * M)`, если эта позиция не была установлена.

Недостатком этого подхода является то, что если массив заполнится, у вас будет больше коллизий.