Случайно наткнулся на этот новый и интересный раздел

Я начну с занятной задачки
Дано : Массив из чисел каждое число в массиве два раза и только одно не имеет пары
Например {21,7,1,4,7,9,21,43,4,43,1} число 9 присутствует один раз. 7,1,4,21,43 имеют пару.

Задача: Найти одиночный элемент в одним циклом

Примечания:
количество елементов известно
0 тоже может быть в массиве smile вообще любое число smile
Найти надо именно число, а не его позицию в массиве smile


Задачка не новая, но занимательная
Это для разминки

Тут ИМХО важно, в каких пределах могут варьироваться числа и какое их количество.

Нет, всё пофиг

Ну, могу предложить такое решение: при вводе ищем назад по массиву. Если такое число уже встречалось, то стираем его (ну например вместо него пишем нуль). Иначе добавлем в массив.

Минусы решения: массив займет много памяти, и очень много времени.

Наверное есть проще решение...

0 тоже может быть в массиве вообще любое число
А как мы узнаем, что такое число уже встречалось?
Добавлено @ 02:04
Кстати, найти надо именно число, а не его позицию в массиве

Млин, встречался я уже с этой задачей, только сейчас на ночь глядя что-то не думается. Завтра...

Времени у нас навалом

А дополнительной памятью пользоватся можно? Например можно создать битовое(2 битовое) множество и добавлять в него найденные элементы. В принципе памяти на доп. структуру уйдет мало.
Добавлено @ 11:14
Я догнал
Можно пробежатся по массиву и соединить все элементы XOR'ом, все двойные исчезнут. Правда работать бдует только если убираемые элементы встречаются четное количества раз, искомый элемнент всего один и встречается не четное количество раз.

Код

Private Sub Command1_Click() strtmp = "" For i = LBound(Mass) To UBound(Mass)   strNext = cStr(Mass(i))   lngPos = InStr(strtmp, strNext)   If lngPos = 0 Then      strtmp = strtmp & Left(strNext & Space(20), 20)   Else      Mid(strtmp, lngPos, 20) = Space(20)   End If Next i Debug.Print Val(Trim(strtmp)) End Sub

Это сообщение отредактировал(а) Akina - 5.11.2004, 11:43

Елки 8 минут потребовалось, а чуть было такие мудрённые структуры и фичи не нагородил

Sardar

Цитата

Можно пробежатся по массиву и соединить все элементы XOR'ом, все двойные исчезнут.

Это очевидно, но работать будет только если ВСЕ элементы - одного типа, скажем целые или одинарной точности... а если Variant?

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

[оффтоп]
Не в обиду сказанно На работе так хлебаю QVB(диалект VB), что только упоминание о нём еще где либо наводит скуку. Сегодня подкинул такую лажу:

Код

sub blabla(test as Double, optional bla as Variant)  if bla then    'большой облом если bla не указан, типа empty это не левый(не числовой) тип    'логично же что если не указан, то это FALSE  end if .... end sub

Приходится извращатся с isMissing и isEmpty, все это во вложенных if'ах, потому как быстрых логических && и || нет, а and и or вычислят оба операндам что приводит к ошибке.

Самый глючный, самый безобразный, самый не удобный, самый обьемный, самый убогий язык...
Ноя говорю не о чистом VB, a o QVB, просто наболело за пару месяцев...
[/оффтоп]

Sardar

Цитата

Действительно работать будет только с целыми числами.

ну необязательно... вещественные типы имеют тоже битовое представление (4-8-10 байт) и их вполне можно ксорить...
Добавлено @ 14:42
Sardar

Код

optional bla as Variant

а такого понятия как значение по дефолту - нету?

Код

optional bla as Variant = False

?

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

Nobody да, но суть задачи - все это сделать за один цикл.