Алгоритъм

Даден е едномерен несортиран масив. (елементите са цели числа)
Трябва да се отговори дали в него има дублиран елемент или не.
Важен е отговора - да или не - кой точно елемент е дублиран няма значение.
Най-простия начин на търсене - да се сравни всеки елемент с всеки при N елемента води до брой операции на сравнение пропорционално на N*N.
Та въпроса е има ли алгоритъм които да е линеен. Тоест с еднократно минаване през масива да може да се отговори?

Минаваш през масива и пълниш елементите му в дърво( или хеш). Ако елемента вече го има в дърво-то (хеш-а) то значи има дублиращи се елементи.

Линейността по принцип не гарантира печалба на бързодействие.

Печалба гарантира спортният тотализатор.

и пълниш елементите му в дърво( или хеш)

Или понеже елементите са цели числа, дори и в масив.

Или обратно пък, пълниш елементите му в едносвързан списък, за да стане по-бавно, за къде се е разбързал пък толкова?! Бързата работа срам за майстора.

той пък хептен не гарантира

Френският тотализатор гарантира.

Ти да не си бил на интервю в Blue Edge?

то пълненето на дърво откога е с константна сложност?

Машина за отделяне на кожа и сланина от парени свине

Ето едно решение с константно време:

#include <math.h>

#include <stdlib.h>

#include <time.h>



typedef int BOOL;



BOOL check_dup(int size, int elem_min, int elem_max){

    srand( (unsigned)time( NULL ) );

        

    if( size > elem_max - elem_min )

        return 1; // princip na chekmedzhetata

    double k = elem_max - elem_min;

    float p = 1 - pow(1-1/k,size-1);

    return (double)rand()/RAND_MAX < p;

}

Сещам се едно линейно решение, ма нема да ти хареса - иска бая памет.

0. Алокираш max-min + 1 бита (може и малко повече)
1. Нулираш ги
2. Вървиш по масива с числата и ако съответния бит е вдигнат - намерил си дублиран елемент - край
иначе - вдигаш го (бита).

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Ми за 32 битово число ше му трябват 512 MB рам.

По скоро около 128 MB. Но гарантира едно минаване само :)

Аре сега, елементарни сметки са тва.

Без изграждане на разни допълнителни структори(заделяне на памет, масиви, хешове) май няма начин. Иначе сравненията са по малки или равни на (н-1)! на брой.

Ако е за структура аз бих ползвал ArrayList. Питаш я дали има такъв елемент вътре, ако няма си го добавяш и така за всеки елемент. Чисто и просто, умните глави са си вкарали алгоритмите за търсене, ние само ги ползваме на готово.

Няма нищо супер алгоритмично или елитно в ArrayList.Contains / Add... ползва се масив и се обикалят елементите.

private object[] _items;





public virtual bool Contains(object item)

{

      if (item == null)

      {

            for (int num1 = 0; num1 < this._size; num1++)

            {

                  if (this._items[num1] == null)

                  {

                        return true;

                  }

            }

            return false;

      }

      for (int num2 = 0; num2 < this._size; num2++)

      {

            if ((this._items[num2] != null) && this._items[num2].Equals(item))

            {

                  return true;

            }

      }

      return false;

}



public virtual int Add(object value)

{

      if (this._size == this._items.Length)

      {

            this.EnsureCapacity(this._size + 1);

      }

      this._items[this._size] = value;

      this._version++;

      return this._size++;

}

--
Increasing Performance By Lowering Expectations.

С алгоритъма на заека и костенурката няма ли да стане тази задача!

Мерси на всички за мненията.
За мен бе ясно от начало, че за да стане по-бързо (т.е. линейно) сигурно трябва да се плати с памет - например втори масив (списък, дърво или някаква каквато и да е структура от данни), където да се натикват елементите и да се проверява при слагане дали вече елемента не е там.
Но при проверката все пак има търсене - тоест сравняване на елемента с вече избраните и не е ясно дали общия брой сравнения ще е линеен. Силно подозирам, че пак ще е пропорционален на N*N а не линеен.

2 eфp. Лyk, писал си:
"Ето едно решение с константно време"
Честно казано не го разбрах :(
(освен това не пиша на C - е, горе-долу разбирам кода, но не разбрах какво прави)

Та накъсо - мислех си, че така поставена задачата няма линейно решение, но реших все пак да попитам - има по-умни от мен хора :) току виж има решение.

"Ти да не си бил на интервю в Blue Edge?"

Не, никъде не съм бил на интервю :)
Просто ме интересува въпроса.

С алгоритъма на заека и костенурката можеш линейно да провериш дали даден свързан списък е цикличен, затова и за тази задача би трябвало да стане.