Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача с массивом / 24 сообщений из 24, страница 1 из 1
20.09.2010, 12:15
    #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:19
    #36855124
egorych
egorych
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача с массивом
abc_da, тупо простым перебором? ;-))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.09.2010, 12:21
    #36855133
rstudio
rstudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача с массивом
просуммировать элементы в массиве С
Сумма массива А умноженая на два минус сумма массива С и будет искомым числом
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.09.2010, 12:47
    #36855207
tanglir
tanglir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача с массивом
rstudio,

это слишком очевидно. М.б. есть какое-то доп. условие? Например, мы не знаем, какие числа были в исходном массиве.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.09.2010, 13:08
    #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:56
    #36855433
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача с массивом
rstudioСумма массива АА мы ее не знаем и вычислить не можем.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.09.2010, 13:59
    #36855446
rstudio
rstudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача с массивом
miksoftrstudioСумма массива АА мы ее не знаем и вычислить не можем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

xor -- 1 проход
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача с массивом / 24 сообщений из 24, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 539ms
Закрыть
start [/forum/topic.php?fid=16&tablet=1&tid=1343440]:
 0ms
get settings:
 9ms
get forum list:
 20ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 179ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 80ms
get tp. blocked users:
 2ms
others: 226ms
total:  539ms
x
x
Закрыть


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