[С++] поиск дубля в массиве - в чем ошибка?

[The Nameless One]

Привет!

Объясните, пожалуйста, в чем ошибка.

Есть массив целых чисел, принимающих значения  от 0 до M.
И только один элемент повторяется.
Надо найти этот элемент.

Вот решение:

Код:

#include <iostream>
using namespace std;

const int N=15;  

typedef unsigned __int64 MyInt64; 

MyInt64 iarray[N]={43, 34, 958, 124, 1234, 82, 623, 73, 9518, 10500, 4389, 515, 9661, 890, 515};


MyInt64 Foo(MyInt64 *m, const int size)
{
	for( int i = 0; i < size - 1; i++ )
			for( int j= i + 1; j < size; j++ ) if( m[i] == m[j] ) return m[i];
	return 0;
}
	

[Sla]

и где ошибка? В чем выражается?

[Алексей++]

всё нормально, только два исправления:

1)  for( int i = 0; i+1 < size; i++ )
2) прототип функции

Код:

bool Foo(MyInt64 *m, const int size,MyInt64& retVal)
{
   for( int i = 0; i+1 < size; i++ )
   {
      for( int j= i + 1; j < size; j++ )
      {
         if( m[i] == m[j] )
         {
              retVal=m[i];
              return true;
         }
      }
   }
   return false;
}

[The Nameless One]

Алексей1153++, спасибо!


Sla, я просто успел поправить (size - 1), до этого был просто size.
Мне сказали, что у меня ошибка в алгоритме. Я подумал, что кроме выхода за пределы должно быть ещё что-то.

[Алексей++]

The Nameless One, в таких случаях, чтоб не путаться, делается всё просто: поскольку j подставляется в индекс массива, а j у нас == i+1 , то нужно индекс и проверить на выход за границу:

i+1<size

[The Nameless One]

Хорошо, учту) Спасибо!

Можно вдогонку вопрос, слегка не в тему?

Как работодатель отнесётся к предложению поработать бесплатно в качестве программиста С++ первое время в целях получения опыта?
т.е. на полную ставку бы не взяли из-за отсутсвия опыта, а так - не слишко ли это тупо предложить?

[Алексей++]

не избалуй работодателя только И обязательно требуй 2-разовое питание + сончас.

[The Nameless One]

Вся понятно)) Не избалую)
Просто как иначе получить опыт в своих краях - не знаю)

[The Nameless One]

Пообщался. Им нужны только опытные разработчики.

И все равно сказали, что в алгоритме ошибка - они даже детали реализации не смотрели :0


Может в этом дело: поиск повторяющегося элемента должен происходит за время O(N).

N - число элементов.

[sss]

Блин, голову сломал. Минимально чего могу придумать O( N log(N)). кто-нибудь знает как сделать O(N) ?

[Алексей++]

у меня приходит в голову только - составлять список уже встреченных элементов (ключ - сам элемент). Когда в очередной раз будет попытка добавить уже существующий в списке элемент, поиск завершён - будет даже меньше, чем ОДИН проход массива , только затраты на работу со списком остаются, правда

[wildCroissant]

2The Nameless One,

честно говоря твой "шеф" прав, у тебя симплифицированная задача, такой в чистом виде в природе не встретишь, и в ТЗ стоит найти ЭЛЕМЕНТ, а ты возвращаешь его ЗНАЧЕНИЕ что не есть хорошо. Алгорит поиска у тебя правильный и самый быстрый и простой, все остальное будет медленнее.
На самом деле тебя проверяют не на умение програмировать, а на умение понимать ТЗ так чтоб шефу не пришлось тебе его обьяснять.

Удачи!

[sss]

wildCroissant, такое ощущение что это Вы дали то ТЗ... Интересно - что значит элемент массива?
Индекс ? Или понятие индекс элемента имеет право на существование?

Алексей1153++,  N^2 будет в худшем случае с дополнительным списком... Я тут думал об алгоритме быстрой сортировки... Причем тоже N^2 будет в худшем случае. Вот! Если дополнительный список упорядоченное б-дерево - тогда log(N). Чёрт, дайте кто-нибудь решение за O(N)!

[wildCroissant]

решение за O(N)-> такого решения не было и не будет! Если увлекаетесь алгоритмами то читайте книжки с таковыми (cookbooks)

[The Nameless One]

Удачи!

Спасибо)

[wildCroissant]

алгоритмами не увлекаемся. Мы ими зарабатываем ))) А увлекаемся девушками

ну прям мушкетеры, один за всех и все за одного, одному пишешь, другие за него отвечают........

[Sla]

еще что нибудь в сторону флуда -  все нахрен удалю

[Вад]

решение за O(N)-> такого решения не было и не будет!

Смотря что считать решением за O(N). Например, если система управления памятью позволяет считать, что выделение обнулённой памяти под вспомогательный массив выполняется за O(C), то алгоритм O(N) существует. Один из вариантов предложил Алексей1153++, также есть и другие алгоритмы (например, "обмен A[i] и A[A[j]] до первой коллизии").

[wildCroissant]

Смотря что считать решением за O(N). Например, если система управления памятью позволяет считать, что выделение обнулённой памяти под вспомогательный массив выполняется за O(C), то алгоритм O(N) существует. Один из вариантов предложил Алексей1153++, также есть и другие алгоритмы (например, "обмен A[i] и A[A[j]] до первой коллизии").

и перфоманц в ms будет O(N)?

.....имелось ввиду машинные циклы........

2Вад, хотя ты прав, что подразумевать, все под конкретный случай смотреть надо

[Вад]

Ну, по крайней мере, если мы говорим о тестовом задании, то задание вполне могло подразумевать просто поиск подобных решений. Которые в реальной жизни едва ли могут дать 100% O(n) для всех случаев (но может реально дать их какой-то частной ситуации, типа N~=M). Но которые, во всяком случае, показывают, что соискатель способен предложить что-то нетривиальное, в сравнении с исходным O(n^2).

[wildCroissant]

не совсем так, исходное решение имеет как ранее говорились O( N log(N)) и не O(n^2)......что касается нетривиальных решений, то не вижу в них особого смысла, даже если алгоритм выглядит на O(n) к примеру с применением листов, вставку и проверку лист будет все равно проводить во всему листу имплицит, возможно еще прийдется сортировать лист для очистки от повторов, и итераций получится не меньше чем  O( N log(N)) , если не больше, с другой стороны этого не видно конечно, все  внутри листа, но на перфоманце скажется также.

[Вад]

По-моему, сложность исходного решения представляет в худшем случае сумму Sum{1, n}(n-i) = n^2 - Sum{1,n}(i) = n^2 - n*(n+1)/2 ~=n(n-1)/2. O(n^2), разве нет? Средний случай, на глаз, будет в 4 раза меньше (Sum{1,n/2}[(n-i)/2]). Даже если не в 4 - всё равно, в не зависящее от n число раз.

Я не говорю, что "нетривиальное" решение означает "мы вот тут используем вставку в map, и плевать на время вставки". Речь идёт исключительно о решениях за один-два прохода по массиву, где любые вспомогательные действия типа вставки в список имеют сложность O(1). Все затраты, выходящие за O(n), находятся за рамками основных манипуляций с массивом, на этапе инициализации.

[wildCroissant]

в общем точно говоря число итераций в исходном варианте равно n(n-1)/2.......
опять таки если разрешается производить инкапсуляцию, то напишем класс, скинем ему поинтер от масива и все решается в одну строчку, сам класс запаковать в длл предоставить как необходимое приложение:))))

[The Nameless One]

Так почему меня не взяли, как считаете?

[The Nameless One]

Ещё ,там речь шла об удалёнке, она мне очень нужна, как воздух. И не взяли  
Просто выпустил свой шанс из рук. Второго такого шанса можно годами ждать.

[Finch]

Тут вопрос. Какой именно максимальное значение может принимать M, в условиях задания

Есть массив целых чисел, принимающих значения  от 0 до M.

Если где то 65536, то скорее всего задание можно решить за один проход массива .

[Finch]

Ну собственно и код

Код:

#include <iostream>
#include <string.h>
using namespace std;

const int N=16;  
const int M=10500;



int array[N]={43, 34, 958, 124, 1234, 82, 623, 73, 9518, 10500, 4389, 515, 9661, 890, 515,74};


int Foo(int *m, const int size)
{
   int res=-1;
   if ((m != NULL) && (size >0))
   {
      char matr[M+1];
      memset(matr, 0, M+1);
      int beg=0;
      while ((beg<size) && (matr[m[beg]] == 0))
      {
         matr[m[beg]]=1;
         beg++;
      }
      if (beg<size) res=m[beg];
   }
   return res;
}
	
int main()
{
   cout << Foo(array, N) << endl;
   return 0;
}

[Вад]

Так почему меня не взяли, как считаете?

Ну, зависит от того, что ты в итоге показал. Вполне возможно, что у нанимателей есть какие-то свои идеи насчёт того, какие именно способности должен демонстрировать человек, выполняя такое задание. А может, просто решили не рисковать. Сейчас, всё-таки, кризис, некоторые поджимаются, и с наймом стажёров, насколько я наблюдаю, не всё радужно. Ума не приложу, куда сейчас идут работать свежеиспечённые выпускники моего ВУЗа.

[The Nameless One]

Finch, класс! Фиг бы я до такого допер! Спасибо.
Единственно, о максимальном значении M ничего не сказано.

Вад, мда, печально. А что за ВУЗ?

[sss]

Finch, прикольно... Вот и решение O(N), как я и просил.

P.S.: А вот если надо вернуть индексы совпадающих элементов ? (так, из вредности)