[DSA] Домашно Linear Data Structures - 8 Задача - Majority Element


1

Условие:

8.The majorant of an array of size N is a value that occurs in it at least N/2 + 1 times. Write a program to find the majorant of given array (if exists).

Та въпросът ми е: Какво правим ако имаме 2 елемента, които се срещат повече от N/2 + 1 път ? И двата ли приемата за мажоранти ?

А ако имаме 2 елемента, които се срещат повече от N/2 + 1 път, но единия се среща повече от другия, кой елемент приемае за мажорант ?

Едит: Ок сега като се замисля въпроса ми беше доста глупав :D

Ето и решението ми:

GitHub

Като цяло - използвам речник за да преброя елементите ( key - елемент, value - брой срещания ) и след това обработва value-тата на речника.




Отговори



2

Source

Едно сравнително простичко решение от мен, отново чрез речник. Мисля, че е най-лесния начин за намиране на Мажорант.


от boncho.vylkov (1923 точки)


1

Решение

Правя речник и после взимам елемента който отговаря на следното условие:

FirstOrDefault(x => dict[x] >= array.Length / 2 + 1)

ако върне 0 значи няма мажорант в дадената редица


от dzhenko (3893 точки)


0
http://pastebin.com/uApH03Zy
Една проверка дали някоя бройка от елементи съвпада с формулата.

от kolchakov96 (237 точки)