Claus7
|
|
1 | |
Проверка числа в большом массиве данных19.02.2013, 19:09. Показов 624. Ответов 2
Метки нет (Все метки)
Здравствуйте.
На собеседовании выдали следующую задача для реализации на С: Дан текстовый файл с 4 миллиардами натуральных чисел, представляющих собой идентификаторы пользователей некой соц. сети. В сети регистрируется новый пользователь, и для него нужно выделить уникальный идентификатор. Т.е. нужно найти число, которого еще нет в файле. При этом даны условия - программа может использовать лишь ограниченное кол-во памяти(1 Гб) и файл может быть прочитан не более 4 раз. Собственно, вопрос - каким образом все это можно реализовать? Я пробовал решить через нахождение максимума среди всех чисел, но было сказано, что максимум int может входить в список чисел. |
19.02.2013, 19:09 | |
Ответы с готовыми решениями:
2
Проверка наличия введенного числа в массиве Функция strtod не изменяет значение errno при слишком большом значении числа Проверка числа в массиве Проверка на повторение числа в массиве |
...
1906 / 1326 / 965
Регистрация: 12.02.2013
Сообщений: 2,172
|
|
21.02.2013, 06:53 | 2 |
Позвольте пару вопросов?:
1. Числа перемешаны? 2. ID могут выпадать? Т.е. к примеру 0, 2, 3 но не будет 1. 3. Перефразируйте, а то не понятно что вы имели в виду:
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
21.02.2013, 11:42 | 3 |
Битовый массив 0.5 Гб.
Сначала обнуляется. Просмотр файла. Число N - N-й бит = 1. Далее ищется 1-й нулевой бит (или последний )
0
|
21.02.2013, 11:42 | |
21.02.2013, 11:42 | |
Помогаю со студенческими работами здесь
3
Проверка нахождения числа в массиве Проверка нахождения числа, введённого с клавы в массиве Как найти число в большом массиве? Быстрый поиск подстрок в большом массиве Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |