ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача с массивом
24 сообщений из 24, страница 1 из 1
Задача с массивом
    #36855110
abc_da
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
abc_da
Гость
Добрый день, озадачили меня на собеседовании такой задачей:

Есть массив целых чисел A, размерностью n. Напр. A=[1,2,3,4,5]
Из него сделали массив B, размерностью 2*n, таким образом: B=[A,A]. Напр. B = [1,2,3,4,5,1,2,3,4,5]
Из массива B выкинули одно число, получился массив С размерностью 2*n-1.
Элементы массива С перемешаны в произвольном порядке .

Задача - определить, какое число было выкинуто ЗА ОДИН ОБХОД массива C.

У меня идей нет, а у вас?
...
Рейтинг: 0 / 0
20.09.2010, 12:15
| Ответить | Цитировать | Написать  
Задача с массивом
    #36855124
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
abc_da, тупо простым перебором? ;-))
...
Рейтинг: 0 / 0
20.09.2010, 12:19
| Ответить | Цитировать | Написать  
Задача с массивом
    #36855133
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
просуммировать элементы в массиве С
Сумма массива А умноженая на два минус сумма массива С и будет искомым числом
...
Рейтинг: 0 / 0
20.09.2010, 12:21
| Ответить | Цитировать | Написать  
Задача с массивом
    #36855207
tanglir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tanglir
Участник
rstudio,

это слишком очевидно. М.б. есть какое-то доп. условие? Например, мы не знаем, какие числа были в исходном массиве.
...
Рейтинг: 0 / 0
20.09.2010, 12:47
| Ответить | Цитировать | Написать  
Задача с массивом
    #36855282
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
Поксоритьнахвесьмассив

Код: plaintext
1.
2.
int n =  0 ;
for(int i= 0 ; i<count; ++i)   n = n ^ a[i];

Парные элементы обнуляются в операции XOR (побитово), а "мистер одиночество" останется как есть в n
...
Рейтинг: 0 / 0
20.09.2010, 13:08
| Ответить | Цитировать | Написать  
Задача с массивом
    #36855433
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
rstudioСумма массива АА мы ее не знаем и вычислить не можем.
...
Рейтинг: 0 / 0
20.09.2010, 13:56
| Ответить | Цитировать | Написать  
Задача с массивом
    #36855446
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
miksoftrstudioСумма массива АА мы ее не знаем и вычислить не можем.

в условиях задачи этого нет.
Основное условие
Задача - определить, какое число было выкинуто ЗА ОДИН ОБХОД массива C.

Но с ХОR тоже вариант крутился в голове, просто не знал получится ли найти элемент.
На собеседовании наверное обязательно предложил или рассказал о своем ходе мыслей.
...
Рейтинг: 0 / 0
20.09.2010, 13:59
| Ответить | Цитировать | Написать  
Задача с массивом
    #36855524
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
abc_da wrote:

на самом деле можно ещё чисто технически решить.

И не применяя условие, что там числа идут подряд. Просто найти за O(N)
непарное число. чисто формально время поиска по хэш-таблице - O(1).
Поэтому идём по массиву и считаем в элементах хэш-таблицы кол-во
повторений. Потом читаем и смотрим где оно на 1 меньше.
Получаем O(N).
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
20.09.2010, 14:29
| Ответить | Цитировать | Написать  
Задача с массивом
    #36856947
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valer
Участник
сумма удвоенного массива = (1 + n ) * n <- ( формула Гаусса)
( число элементов массива после удвоения четное)
за один проход массива С считаем его сумму
разница = выкинутое число
...
Рейтинг: 0 / 0
21.09.2010, 11:06
| Ответить | Цитировать | Написать  
Задача с массивом
    #36857002
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Valerсумма удвоенного массива = (1 + n ) * n <- ( формула Гаусса)Про этот момент можно поподробнее?
...
Рейтинг: 0 / 0
21.09.2010, 11:21
| Ответить | Цитировать | Написать  
Задача с массивом
    #36857119
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valer
Участник
Гаусс когда был маленьким ребенком ( 10-12 лет) он
нашел формулу для суммы массива целых чисел от 1 до N
идея проста
сложить первый и последний элемент =( 1 + N )
+
сложить второй и предпоследний элемент = ( 2 + N - 1 ) = ( 1 + N )
и т.д.
всего таких пар N/2 четных N
или (N-1)/2 для нечетных, но тогда остается центральный элемент
формула легко обобщается если не массив начинается не с 1
...
Рейтинг: 0 / 0
21.09.2010, 11:51
| Ответить | Цитировать | Написать  
Задача с массивом
    #36857146
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Valerформулу для суммы массива целых чисел от 1 до NВ условии задачи не сказано, что массив А заполнен последовательными числами от 1 до N.
...
Рейтинг: 0 / 0
21.09.2010, 12:06
| Ответить | Цитировать | Написать  
Задача с массивом
    #36857296
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valer
Участник
Есть массив целых чисел A, размерностью n. Напр. A=[1,2,3,4,5]

в первом топике
...
Рейтинг: 0 / 0
21.09.2010, 12:42
| Ответить | Цитировать | Написать  
Задача с массивом
    #36857299
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
ValerЕсть массив целых чисел A, размерностью n. Напр. A=[1,2,3,4,5]

в первом топикеОбратите внимание на слово "Напр", оно означает "например".
...
Рейтинг: 0 / 0
21.09.2010, 12:43
| Ответить | Цитировать | Написать  
Задача с массивом
    #36857366
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Вопрос в том, что вы пытаетесь определить - само число или его положение, "номер элемента в массиве", так сказать. Число, действительно, решается элементарной суммой - "за один проход" как раз и подразумевает, что сумму элементов массива вы сможете вычислить. А вот положение в один проход невозможно вычислить хотя бы потому, что был применён рандом к массиву B - пропало любое однозначное отображение A->B...
...
Рейтинг: 0 / 0
21.09.2010, 13:07
| Ответить | Цитировать | Написать  
Задача с массивом
    #36857390
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
AndreTMбыл применён рандом к массиву B - пропало любое однозначное отображение A->B...Хм, мне казалось, что B=[A,A] - это никак не рандом.
...
Рейтинг: 0 / 0
21.09.2010, 13:15
| Ответить | Цитировать | Написать  
Задача с массивом
    #36857433
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Соврал. Отображение A(B)->C.
...
Рейтинг: 0 / 0
21.09.2010, 13:24
| Ответить | Цитировать | Написать  
Задача с массивом
    #36857450
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Еще раз соврал.
B(A)->C
...
Рейтинг: 0 / 0
21.09.2010, 13:27
| Ответить | Цитировать | Написать  
Задача с массивом
    #36857839
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valer
Участник
Обратите внимание на слово "Напр", оно означает "например".

корректно ответить последовательные числа или нет
может только автор топика.
напрмер, он не стал набирать [ 1,2,3,4,5,6,7].

+ зачем тогда еще и перемешивать ?
скорее всего, если набор произвольный, то решения за 1 проход нет
...
Рейтинг: 0 / 0
21.09.2010, 14:47
| Ответить | Цитировать | Написать  
Задача с массивом
    #36857857
Берлuнгер
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Берлuнгер
Участник
ValerОбратите внимание на слово "Напр", оно означает "например".

корректно ответить последовательные числа или нет
может только автор топика.
напрмер, он не стал набирать [ 1,2,3,4,5,6,7].

+ зачем тогда еще и перемешивать ?
скорее всего, если набор произвольный, то решения за 1 проход нет

xor чем не устраивает? (решение ЯрМеча) ?
...
Рейтинг: 0 / 0
21.09.2010, 14:49
| Ответить | Цитировать | Написать  
Задача с массивом
    #36857890
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
БерлuнгерValerОбратите внимание на слово "Напр", оно означает "например".

корректно ответить последовательные числа или нет
может только автор топика.
напрмер, он не стал набирать [ 1,2,3,4,5,6,7].

+ зачем тогда еще и перемешивать ?
скорее всего, если набор произвольный, то решения за 1 проход нет

xor чем не устраивает? (решение ЯрМеча) ?Наверно, тем, что для ознакомлением с этим решением придется (в поисках оного) прочесть весь топик
...
Рейтинг: 0 / 0
21.09.2010, 14:54
| Ответить | Цитировать | Написать  
Задача с массивом
    #36858205
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valer
Участник
согласен, XOR решение универсальное
...
Рейтинг: 0 / 0
21.09.2010, 15:54
| Ответить | Цитировать | Написать  
Задача с массивом
    #36858868
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Valer wrote:

> + зачем тогда еще и перемешивать ?
> скорее всего, если набор произвольный, то решения за 1 проход нет

Да есть. Я ж писал. Ну ладно, не за один, за два. Но это мелочи.
всё равно O(n)
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
21.09.2010, 20:26
| Ответить | Цитировать | Написать  
Задача с массивом
    #36859533
Берлuнгер
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Берлuнгер
Участник
MasterZiv
Valer wrote:

> + зачем тогда еще и перемешивать ?
> скорее всего, если набор произвольный, то решения за 1 проход нет

Да есть. Я ж писал. Ну ладно, не за один, за два. Но это мелочи.
всё равно O(n)

xor -- 1 проход
...
Рейтинг: 0 / 0
22.09.2010, 11:18
| Ответить | Цитировать | Написать  
24 сообщений из 24, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача с массивом
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36857146&tid=1343440]:
 0ms
get settings:
 7ms
get forum list:
 10ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 171ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 36ms
get tp. blocked users:
 1ms
others: 225ms
total:  463ms
созд. / загр.: 463ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]