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

Я начну с занятной задачки
Дано : Массив из чисел каждое число в массиве два раза и только одно не имеет пары
Например {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 да, но суть задачи - все это сделать за один цикл.

 Да, это не подходящее решение, не правильно понял условие. 

Это сообщение отредактировал(а) Evergreen - 23.5.2007, 20:55

[злостный оффтоп]
Akina к сожалению такй подход не работает
Все таки QVB гораздо более убогий чем просто VB. Ксатати как в чистом VB делать callback функции и динамически импортировать модули? Еще перегрузки функций не хватает...
Извиняюсь перед участниками за этот оффтоп
[/злостный оффтоп]

Цитата(maxim1000 @ 6.11.2004, 11:30)

так что при добавлении к очереди смотрим, не встречается ли там уже такой массив

Цитата(Nobody @ 7.11.2004, 15:03)

Посмотрю, есть ли в моём втором массиве оно или нет.

Ребята в теории всё замечательно Но КАК смотреть в очереди или массиве без цикла?

Итак ответ на Си++:
Победитель - Sardar.

Код

template <class NUMBER> NUMBER find(NUMBER * massiv, unsigned length) { NUMBER res=massiv[0]; for(unsigned i=1;i<length;i++){res^=massiv[i];} return res; }

Пожалуйста, сообщайте ваши персональные ответы сюда, только если ваш ответ будет элегантнее представленного
[s]

Цитата(ALEXANDRO @ 9.11.2004, 17:26)

на PHP

Гы-Гы Считай, что тоже самое

Код

<? function find($massiv) { $res=$massiv[0]; for($i=1;$i<count($massiv);$i++){$res^=($massiv[$i]);} return $res; } print("Ответ: ".find(array(21,7,1,4,7,9,21,43,4,43,1))); ?>

А что значит ^=?

Цитата(Secandr @ 9.11.2004, 20:50)

А что значит ^=?

это присваивание с исключающим ИЛИ,
a^=b грубо говоря a=a XOR b
но у меня такое чувство, что в стандартном С++ такого оператора нет.

Это сообщение отредактировал(а) Perchilla - 9.11.2004, 21:05

Цитата(Perchilla @ 9.11.2004, 20:03)

в стандартном С++ такого оператора нет

Как нет? Ксор был есть и будет есть

Ксор одинаковые биты 0,0 или 1,1 скидывает на 0, остаются только разные например:

100101^
111101
011000

То есть, два одинаковых числа дадут 000000 Таким образом остаётся только число, которое не имеет пары
ПС:
А ещё Ксор это функция сложения векторов в Z2

А ещё её можно записать так

Код

$res=((~$res)&$massiv[$i])|($res&(~$massiv[$i]));

Поскольку ксор это (~А&B)|(~B&A)

Цитата

Создать второй массив. Когда число встречается первых раз, записывать его в этот массив. Когда число встречается второй раз, удалять

Интересно а как ты будешь узнавать есть ли в массиве это число?

Код

#!/usr/bin/perl @arr = qw( 21 7 1 4 7 9 21 43 4 43 1 ); map { $temp{ $_ }++ } @arr; %temp = reverse %temp; print $temp{ 1 };

Работать будет только в том случае, если в массиве только одно число не имеет пары, все остальные числа могут быть в любом количестве, больше одного.

Это сообщение отредактировал(а) korob2001 - 1.12.2004, 20:30

Цитата(korob2001 @ 1.12.2004, 19:28)

Работать будет только в том случае, если в массиве только одно число не имеет пары, все остальные числа могут быть в любом количестве, больше одного.

Ну korob2001, map юзать нечестно! Так я любую проблему в финкцию запихаю, а потом скажу, что она решается одним действием.

Экстремальный вариант:

quicksort(@array)

дальше проходим массив и смотрим - если это первый элемент - следующий, если элемент Н = элементу Н-1, тогда следующий, элсе - ответ...;)

cybear Если H <> H+1 и H <> H-1

Цитата(cybear @ 1.12.2004, 22:23)

quicksort(@array)

Цитата(sergej @ 1.12.2004, 22:20)

Так я любую проблему в финкцию запихаю, а потом скажу, что она решается одним действием.

Цитата

Ну korob2001, map юзать нечестно! Так я любую проблему в финкцию запихаю, а потом скажу, что она решается одним действием.

А чем map хуже цикла? Можно вместо map поставить for и при этом мы ещё избавимся от двух фигурных скобок. Вот пример:

Код

#!/usr/bin/perl @arr = qw( 21 7 1 4 7 9 21 43 4 43 1 ); $temp{ $_ }++ for @arr; %temp = reverse %temp; print $temp{ 1 };

Можно и while:

Код

#!/usr/bin/perl @arr = qw( 21 7 1 4 7 9 21 43 4 43 1 ); $temp{ $_ }++ while ( $_ = shift @arr ); %temp = reverse %temp; print $temp{ 1 };

А вот foreach:

Код

#!/usr/bin/perl @arr = qw( 21 7 1 4 7 9 21 43 4 43 1 ); $temp{ $_ }++ foreach @arr; %temp = reverse %temp; print $temp{ 1 };

Просто, Perl делает свою работу и вариантов, как всегда, несколько. ;))))

Это сообщение отредактировал(а) korob2001 - 2.12.2004, 05:06

Код

@a = qw( 21 7 1 4 7 9 21 43 4 43 1 ); $c{$_}++  for @a; for (keys %c) { push @d, $_  if $c{$_} == 1 } print "@d";

это я был

Кстати korob2001 а что будет если начальный массив будет иметь > одного одиночного елемента ? ;)

уверен что ваше решение несработает.


Удалось таки убрать скобки

Код

@a = qw(8 21 7 1 4 7 9 21 43 4 43 1 ); $c{$_}++  for @a; push @d, $c{$_} == 1 ? $_ : next for keys %c; print "@d";

А вот за один проход ... тока отсортировать надо

Код

@a = qw(8 21 7 1 4 7 9 21 43 4 43 1 ); @a = sort {$a <=> $b } @a; for (my $i = 0; $i < @a; $i += 2) {    push @d, $a[$i] != $a[$i+1] ? $a[$i--] : next } print "@d";

Это сообщение отредактировал(а) ElectricalStorm - 13.12.2004, 04:04

Цитата

Кстати korob2001 а что будет если начальный массив будет иметь > одного одиночного елемента ? ;)

О том, что будет читай выше.

Цитата

@a = qw(8 21 7 1 4 7 9 21 43 4 43 1 ); $c{$_}++  for @a; push @d, $c{$_} == 1 ? $_ : next for keys %c; print "@d";

Нормально, но вся проблема в том, что здесь два цикла, а нужо <= 1. Так написано в условии. ;)))))

Цитата

@a = qw(8 21 7 1 4 7 9 21 43 4 43 1 ); @a = sort {$a <=> $b } @a; for (my $i = 0; $i < @a; $i += 2) {   push @d, $a[$i] != $a[$i+1] ? $a[$i--] : next } print "@d";

Решение отличное, но здесь человека, начавшего эту тему, может смутить вот эта строка:

Код

@a = sort {$a <=> $b } @a;

потому как такой пример не подошёл:

Код

#!/usr/bin/perl @arr = qw( 21 7 1 4 7 9 21 43 4 43 1 ); map { $temp{ $_ }++ } @arr; %temp = reverse %temp; print $temp{ 1 };

Это сообщение отредактировал(а) korob2001 - 13.12.2004, 07:57

Код

k:=1; for i:=1 to n do begin if A[k]=A[i+1] then  begin   delete(A[k]);   delete(A[i+1]);   i:=1;   k:=1  end else ShowMessage('а вот оно - число'+A[k]); end;

должно работать.

Это сообщение отредактировал(а) ALEXANDRO - 19.12.2004, 02:53

опять забыл зайти по нормальному . В общем это ^ моё. ( то что наверху)

Vladimir13
мы юзаем теги {code} и пишем, что за язык
Добавлено @ 02:53
надеюсь я прально понял, это Delphi?

Цитата(ALEXANDRO @ 19.12.2004, 02:52)

надеюсь я прально понял, это Delphi?

ведь понял же . Где умею там и пишу.

Vladimir13
я, может, и понял, только вот кто-то другой наверняка не понял... ведь не так трудно написать, да?

ну, извините, учту на будущее.