хранение случайных значений в массивах с учетом дубликатов - PullRequest
2 голосов
/ 15 февраля 2011

Это новая версия этого поста , чтобы отделить вопрос программирования от вопроса вероятности.

Я хочу сохранить номер, например, 25 случайно сгенерированных чисел от 1 до 365 в массиве. Но мне нужно отслеживать дубликаты. Вот как я думал об этом:

  • создать 4 массива: основной массив, массив для 2 дубликатов, массив для 3 дубликатов и один для более чем 3 дубликатов

  • добавить каждое сгенерированное число одно за другим в мастер-массив. Но прежде чем сделать это, просмотрите массив, чтобы увидеть, есть ли он там. Если это так, добавьте его во второй массив, но перед этим повторите описанный выше процесс и т. Д.

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

это не очень эффективный алгоритм. Есть предложения по улучшению?

Может ли мой предложенный подход считаться большим O (n), то есть линейным?

Ответы [ 4 ]

2 голосов
/ 15 февраля 2011

Почему вы используете массивы? Казалось бы, HashMap или другая структура карты имеет больше смысла. Вот как бы я это сделал.

  1. Создание новой пустой хэш-карты из дней рождения в целые числа
  2. Создать случайный день рождения.
  3. Проверьте, есть ли день рождения в хэш-карте. Если это не так, добавьте его со значением «1». Если это так, увеличьте значение в этот день рождения.

Теперь вы можете получить количество уникальных дат, сгенерированных по количеству ключей в хэш-карте, и любую информацию о количестве дубликатов из значений.

1 голос
/ 15 февраля 2011

Вот как я думаю, что проблема может быть решена.

  1. Имеет два массива: основной, содержащий дни рождения, и один, содержащий количество повторений.
  2. Создание случайного дня рождения.
  3. Цикл поосновной массив и посмотрите, есть ли он там.
  4. Если его там нет, добавьте его в основной массив и в той же позиции индекса сохраните 1 в другом массиве.(Если вы добавите день рождения мастеру [3], сохраните 1 под номером [3])
  5. Если он уже существует, добавьте его к соответствующему индексу в другом массиве.
  6. СейчасВаш основной массив будет содержать сгенерированные дни рождения, а соответствующие индексы в другом массиве будут иметь количество повторений.(мастер [0] имеет дату, а число [0] - количество повторений даты).

Надеюсь, это поможет.

0 голосов
/ 15 февраля 2011

В зависимости от того, сколько раз вам понадобится сгенерировать случайный список, вы можете создать список всех чисел и затем использовать случайную сортировку , чтобы переставить их, затем вы можете вытянуть последовательные блоки с массив, который будет как в случайном порядке, так и уникальным. Таким образом, в худшем случае производительность будет O (размер всех чисел) + O (размер необходимых чисел), а лучший вариант O (размер необходимых чисел). Пример:

private int[] numbers;
private int numberIndex=Integer.MAX_VALUE;
private void initNumbers(){
  int[] numbers = new int[365];
  for(int i=0;i<365;i++){
    numbers[i] = i+1;
  }
  shuffleSort(numbers);
  numberIndex = 0;
}

public int[] getRandom(int howMany){
  if(numberIndex > numbers.length-howMany){
    initNumbers();
  }
  int[] ret = new int[howMany];
  for(int i=0;i<howMany;i++){
    ret[i] = numbers[numberIndex++];
  }
  return ret;
}

private void shuffleSort(int[] numbers){
  Random r = new Random();
  int tmp=0, swap=0;
  for(int i=numbers.length-1;i>0;i--){
    swap = r.nextInt(i);//random number between 0 and i
    tmp = numbers[i];
    numbers[i] = numbers[swap];
    numbers[swap] = tmp;
  }
}

}

0 голосов
/ 15 февраля 2011

в рубине:

birthdays = {}.tap{|h| h.default = 0}
25.times { birthdays[rand(364)+1] += 1 }

puts birthdays.keys # all the uniq birthdays
puts birthdays.inspect # all birthdays with counts

Идея состоит в том, чтобы использовать хеш или массив фиксированного размера, где ключи соответствуют дням рождения, а значения - сколько раз этот день был выбран

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

birthdays.keys.shuffle
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...