Алгоритм сохранения элементов в порядке поддержания массива

Question

У меня есть один генератор случайных чисел, который генерирует число между 1 to k. Также у меня есть массив из int типа (например, int[]), размер которого составляет N, где k меньше, чем N.

Теперь проблема в том, что мне нужно сохранить уникальные сгенерированные числа в массив (отклонение сгенерированного дублированного числа) и поддерживать порядок сгенерированных чисел, не используя лишнее пространство и в сложности O(N). i.e в том же массиве мне также нужно поддерживать порядок сгенерированного числа. Так что я могу получить их в сгенерированном порядке. Никакой битмап или дополнительный массив и т. Д. Не предполагается использовать.

Его не домашнее задание. Это один из вопросов интервью. Я не должен использовать лишнее пространство. Он попросил меня использовать тот факт, что k меньше, чем N, и вам нужно внедрить поведение хэшмапа в том же массиве. Я предложил множество алгоритмов, используя дополнительные пробелы, но он отклонил также использование сортировки, но я не смог поддерживать сгенерированный порядок.

Answer 1

Хорошо, я куплю это не домашнее задание. Вот решение. Пусть к = 3, N = 5

Старт:

ar[0] = 0 
ar[1] = 0 
ar[2] = 0 
ar[3] = 0 
ar[4] = 0 

Генерировать случайное число. Предположим, что это 2. Нам нужно сохранить два бита информации:

• «2» - это первое случайное число.
• «2» взят.

Так что мы делаем это:

ar[0] = 2 
ar[1] = 0 
ar[2] = 10 // 10 is any number that's larger than N. 
ar[3] = 0 
ar[4] = 0 

следующий номер: 4

ar[0] = 2 
ar[1] = 4 
ar[2] = 10 // taken 
ar[3] = 0 
ar[4] = 10 // taken 

следующий номер: 2

ar[2] >= 10 thus taken, try another number 

следующий номер: 1

ar[0] = 2 
ar[1] = 14 // added 10 to signify it's taken 
ar[2] = 11 // added 1 as it's the current number 
ar[3] = 0 
ar[4] = 10 // taken 

Выполнено.

Теперь, перебирать массив и вычесть 10 из всего, что это больше, чем 10. Вы будете в конечном итоге с

ar[0] = 2 
ar[1] = 4 
ar[2] = 1 
ar[3] = 0 
ar[4] = 0 

один нюанс - это предполагает, что случайные числа в диапазоне [1..N]. если они [0..N-1], вам придется немного подправить.