Разлічыць кантрольны элемент масіва

На мінулым тыдні я з'явіўся ў адным з інтэрв'ю. Я атрымаў наступнае пытанне:

<�Р> Улічваючы масіў з 2n элементаў, і з гэтага п элементаў з'яўляюцца такімі ж, а астатнія ўсе розныя. Знайсці элемент, які паўтараецца п раз.      <�Р> Там няма абмежавання на дыяпазон элементаў. </Р>

Можа хто-то калі ласка, дайце мне эфектыўны алгарытм для вырашэння гэтага?

2
<�Б> <�з аддаленага адказу> ў раздзеле гэта .
дададзена аўтар Dukeling, крыніца

7 адказы

«Масіў 2n элементаў дадзены, і з гэтага п элементы аднолькавыя, а астатнія ўсе розныя. Знайдзіце элемент, які паўтараецца п раз.»

Гэта можа быць зроблена ў O (N) па наступным алгарытме:

1) ітэрацыю масіва, правяраючы, каб убачыць, калі якія-небудзь элементы [I] і [+ 1] з'яўляюцца аднолькавымі.

2) ітэрацыі па масіве, правяраючы, каб убачыць, калі якія-небудзь элементы [I] і [I + 2] з'яўляюцца аднолькавымі.

3) Калі п = 2 (і, такім чынам, даўжыня = 4), праверце, калі 0 і 3 з'яўляюцца аднолькавымі.

тлумачэнне:

Выклік ўзгадняючых элементаў м і ня-узгадняючыя элементы г.

Пры п = 2, то можна пабудаваць mmrr, mrmr і MRRM - таму мы павінны праверыць памер зазору 0, 1, і адзінае месца, дзе мы можам мець памер зазору 2.

For n > 2, we cannot construct the array with no gaps of size 0 or 1. For example for n = 3, you have to start like this: mrrmr... but then you must place an m. Similarly for n = 4, mrrmrrmm - having no gaps of size 0 or 1 would require ms to be outnumbered by rs by more and more as n increases. Proving this is easy.

7
дададзена
Гэта добрая ідэя, і asympotically аптымальна, але вы можаце атрымаць больш рычагоў, калі крок-не атрымоўваецца (не ўтрымлівае паслядоўную пару). У прыватнасці, калі гэта не так, мэтавай элемент павінен быць ідэнтыфікаваныя з выкарыстаннем толькі першыя чатыры элемента. Глядзіце мой адказ.
дададзена аўтар Andrew Tomazos, крыніца
Ці можаце вы даць мне гэта доказ. На самой справе патрабуе матэматыку, і некаторыя заявы. Ці можаце вы сказаць мне, што?
дададзена аўтар devsda, крыніца
Цяпер я атрымаў гэта :) Вялікі дзякуй
дададзена аўтар devsda, крыніца
@devsda Гэта трывіяльнае доказ ад адваротнага.
дададзена аўтар Patashu, крыніца

Вам проста трэба знайсці два элемента, якія з'яўляюцца аднолькавымі.

Адна з ідэй будуць:

Атрымаць адзін элемент з 2n элементаў.
Калі гэта не ў выглядзе набору, змесціце яго ў.
Паўтарайце датуль, пакуль не знойдзеце той, які знаходзіцца ў гэтым наборы.

3
дададзена
Я не атрымаць другую кропку. Калі ласка, растлумачце яшчэ раз: «Калі гэта не ў выглядзе набору, змесціце яго ў.»
дададзена аўтар devsda, крыніца
Вы павінны памятаць, лік ўжо атрымалі. г.зн. змясціць іх у набор.
дададзена аўтар Burkhard, крыніца
Гэта, здаецца, як самы лепшы варыянт. Праблема ў асноўным сцвярджае, што існуе N + 1 розных лікаў з якіх адзін паўтараецца N раз. Верагоднасць таго, што наступны элемент абраны не з'яўляецца ўжо ў наборы падае толькі як больш дадаюцца ў набор і, як N становіцца больш, так што ў сярэднім гэта павінна зрабіць нашмат лепш, чым O (N). Потым яшчэ раз, што можа азначаць, што гэта не строга O (N).
дададзена аўтар Nuclearman, крыніца

Калі першыя чатыры элемента розныя, то масіў павінен змяшчаць запар пару мэтавага элемента ...

int find(int A[n])
{
   //check first four elements (10 iterations = O(1))
    for (int i = 0; i < 4; i++)
       for (int j = i+1; j < 4; j++)
          if (A[i] == A[j])
              return A[i];

   //find the consecutive pair (n-4 iterations = O(n))
    for (int i = 3; i < n-1; i++)
        if (A[i] == A[i+1])
            return A[i];

   //unreachable if input matches preconditions
    throw invald_input;
}

Гэта аптымальна Аб (п) за адзін праход і O (1) прасторы.

1
дададзена

Ну, калі складанасць не мае значэння, адзін наіўны спосаб будзе выкарыстоўваць дзве завесы, што ў найгоршым выпадку O (N ^ 2).

for(int i = 0; i < array.size(); i++){
    for(int j = i + 1; j < array.size(); j++){
        if(array[i] == array[j]){
          //element found
    }
}
1
дададзена
У інтэрв'ю пытанні, як гэта, складанасць у прыватнасці, не мае значэння. Яны хочуць, каб у ідэале асімптатычна аптымальнае рашэнне, пераважна за адзін праход, і накід доказы на прадмет правільнасці.
дададзена аўтар Andrew Tomazos, крыніца
Гэта не атрымала б вам працу ...
дададзена аўтар Dukeling, крыніца

У вас ёсць масіў 2n элементаў і паловы аднолькавыя і астатнія адрозніваюцца так, разгледзім наступны выпадак,

ARRAY[2n] = {N,10,N,878,85778,N......};

або

Array[2n] = {10,N,10,N,44,N......};

And so on now simple case in fабоloop like,

if(ARRAY[i] == ARRAY[i+1])
{
         //Your similar element :)
}
0
дададзена
Не працуе для 1,2,1,3,1,4 . Вы павінны праверыць я + 2 , а таксама, як і ў Patashu ў адказ .
дададзена аўтар Dukeling, крыніца

Калі вы знайшлі адзін элемент у два разы, то ёсць элемент, як кажа пытанні: Масіў 2n элементаў дадзена, <�моцны> і з гэтага п элементаў аднолькавыя, а астатнія ўсе розныя . Знайсці элемент, які паўтараецца п раз.

0
дададзена
Як вы будзеце сачыць элементы такім чынам, вы ведаеце, ці знайшлі вы які-небудзь дадзены элемент раней?
дададзена аўтар Dukeling, крыніца

Я думаю, што гэтая праблема павінна быць «знайсці элемент, які з'яўляецца па меншай меры п + 1 раз», калі яна з'яўляецца толькі ў п раз яны могуць быць два.

Калі выказаць здагадку, што існуе такі элемент на ўваходзе наступны алгарытм можа быць выкарыстаны.

input array of 2*n elements;

int candidate = input[0];
int count = 1;

for (int i = 1; i < 2*n; ++i) {
    if (input[i] == candidate) {
         count++;
    } else {
         count --;
         if (count == 0) candidate = input[i];
    }
}

return candidate;

калі запыт, каб знайсці, калі ёсць элемент прысутнічае п + 1 раз іншы абыход патрабуецца, каб знайсці, калі элемент знойдзены на папярэднім кроку з'яўляецца п + 1 раз.

<�Моцны> Edit:

Было выказана меркаванне, што п элементаў з аднолькавым значэннем з'яўляюцца сумежнымі. Калі гэта так проста выкарыстоўваць вышэйзгаданы алгарытм і спыняецца, калі лічыльнік дасягае п.

0
дададзена
Гэта не працуе. Разгледзім {1,2,1,3} . Ваша праграма будзе няправільна выхад 3. Далей я мяркую, што ёсць лагічная памылка ў вашым звароце рахунку. Гэты алгарытм ад Fisher-Salzberg (1982) «Знаходжанне большасці сярод рускіх галасоў.» Часопіс алгарытмаў 3, стар 143-152. У той час як яна можа быць адаптаваная, яна не скарыстацца іншы паловай элементаў, якія з'яўляюцца розныя.
дададзена аўтар Andrew Tomazos, крыніца
@MariusBucur: Ваш апошні каментар сэнсу да кропкі быцця неспасціжна. Калі ласка, арганізаваць свае думкі і паспрабаваць яшчэ раз.
дададзена аўтар Andrew Tomazos, крыніца
Пытанне абвяшчае, што ўсе астатнія элементы розныя. Так з'яўляецца п раз нармальна.
дададзена аўтар Dukeling, крыніца
@ User1131467 пытанняў не прапануе мне, што п элементы з аднолькавым значэннем з'яўляюцца сумежнымі. Улічваючы гэта праблема павінна заявіць, што павінна з'явіцца п + 1 раз. Калі яны з'яўляюцца сумежнымі гэта вельмі проста, проста выкарыстоўвайце вышэй Algo і спыняецца, калі лічыльнік роўны п.
дададзена аўтар Marius, крыніца