[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-тата на речника.




Отговори



4
Не е възможно да имаш два елемента, които се срещат повече от (N/2 + 1) пъти в масив от N елемента.

от pirin (1101 точки)


0
Ок, въобще не се замислих за това. В момента се чувства доста тъпо :D

от Teodor92 (13062 точки)


1

Не можем да имаме 2 елемента, които се срещат N/2 + 1, защото това е повече от половината. Или имаме мажорант, или не.

Ето го моето решение: цък

Използвам хеш-таблица, в която ключ са ми числата и при всяко повторение увеличавам стойността за дадения ключ. След това се обхождат двойките и ако имам ключ със стойност >= n/2+1 връщам мажорант.


от georgi.ivanov (3261 точки)


12

Решение: source.

Използвам един ефективен алгоритъм, описан в глава "7.2. Мажорант" от книгата "Програмиране = ++Алгоритми;".

Цитат: "Започваме с празен стек, в който в началото постъпва първият елемент на масива. След това на всяка стъпка от масива се извлича следващият елемент и се сравнява с елемента на върха на стека. Ако елементите са еднакви, новият елемент постъпва в стека. В противен случай, се изключва елементът на върха на стека, което практически означава отхвърляне и на двата елемента. В случай на празен стек следващият елемент постъпва в него. Процесът продължава до изчерпване елементите на масива. Ако има мажорант, той е на върха на стека. Наистина, елементите се унищожават едновременно по двойки, при това само ако са различни. Така, мажорантът не може да бъде унищожен, защото няма достатъчно немажорантни елементи в масива."

Вместо стек, използвам обикновена променлива, която увеличавам или намалявам с единица.


от jasssonpet (6814 точки)


1

Решение: Github

В класа Utils.cs има extension метод, който сравнява стойностите на поредицата и при съвпадение увеличава counter.

Ако counter е равен на числото от формулата го връщам, ако не нулирам counter-a и проверявам следващото.


от kirov (4821 точки)


0
Целта е, не да работи с масиви, а с листове ( не че има огромна разлика ).

от Teodor92 (13062 точки)

0
Масивите пак са линейна структура :D С листове става прекалено лесно, а аз съм мазохист, знаеш.

от kirov (4821 точки)



2

http://pastebin.com/Z1JJuqrC

Аз малко cheat-вам със LINQ, но ми изглежда доста по-елегантно отколкото да въртя вложени цикли :D


от VGeorgiev (2890 точки)


0
Е LINQ нали за улеснение е направен :Д Аз също в домашните от тази тема доста го ползвам.

от v.staykov (212 точки)

0
Здравей, ти проверяваш дали точно толкова пъти се повтаря, а те може да са и повече. Може да използваш .FirstOrDefault() и да подаваш условието.

от jasssonpet (6814 точки)



1
Добре кво му е на едно такова решение примерно?
 
 
Взимам първия елемент и търся в листа за други такива. Понеже е LinkedList това става много по-бързо. Ако намери направо ги премахва, което също е бързо за LinkedList. Лист-а намалява и на следващия цикъл LinkedList.First() вече е съвсем друго число, защото старите са премахнати. Действията се повтарят, докато не се намери Majorant-a или просто не се изчист лист-а

от plamentsokov (105 точки)


0
Махането може да ти е бързо, но търсенето и обхождането е проблемно. Представи си че имаш сортирана редица от елементи, която има мажоранта. Обаче мажорантата започва от n/2-1 вата позиция (най-късната възможна). Това ти е най-лошият случай и бързодействието няма да ти е добро. Ако не бъркам ще е нещо от сорта на O(n^2), защото при проверката на всеки елемент обхождането започва отначало. Даже може и да е повече, защото Remove() май започва обхождането отначало, но може и да бъркам...зависи от имплементацията на LinkedList в .NET

от gallumbits (2371 точки)

0
Даже можеш да направиш една проверка и сравнение на решенията със Stopwatch за да провериш скоростта.

от gallumbits (2371 точки)



1

Направил съм две решения, ето ги и тях:

Решение:

http://pastebin.com/nvVyGMG8

Накратко първо въвеждам брой на числата в масива и след това ги прочитам като правя проверки дали входа е правилен както за броя така и за елементите. Програмата не приключва при грешен вход

Второто решение е закоментирано, защото е почти същото с Dictionary(). Напълвам речника с ключове елементите и стойности броя срещания и намирам мажоранта ако го има.

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

try
        {
            int majorant = numbersSet.First(setElement => (numbersList.FindAll(
                listElement => listElement == setElement).Count >= majMinOccurs));
            Console.WriteLine(majorant);
        }
        catch
        {
            Console.WriteLine("No majorant!");
        }

или един вид това казва следното: от сета намери ми този елемент, който е такъв че броя на срещанията му в листа да е >= N / 2 + 1


от s_mihaylov (0 точки)


0

LINQ си е предназначено за улеснение на програмистите и не мисля, че е cheat-ване wink

static void Main(string[] args)
        {
            //List<int> numbers = new List<int> { 4, 2, 2, 5, 2, 3, 2, 3, 1, 5, 2 };      //No majorant     
            List<int> numbers = new List<int> { 2, 2, 3, 3, 2, 3, 4, 3, 3 };           //Majorant 3
            var majorant = numbers.ToLookup(x => x).Where(xs => xs.Count() >= numbers.Count/2+1);
            StringBuilder sb = new StringBuilder();
            foreach (var item in majorant)
            {
                sb.AppendLine(item.Key.ToString());
            }
 
            string result = sb.ToString() == string.Empty  ? "No majorant" : sb.ToString();
            IEnumerable<IGrouping<int,int>> majorantLINQ = numbers.ToLookup(x => x).Where(xs => xs.Count() >= numbers.Count/2+1);
            var majorant = majorantLINQ.FirstOrDefault();
            string result = majorant == null ? "No majorant" : majorant.Key.ToString();     
            Console.WriteLine(result);
        }


0
Защо ползваш StringBuilder и защо въртиш цикъл по majorant при положение, че той може да има най-много един елемент?

от pirin (1101 точки)



1

Решение.
Използвам Dictionary, в което вкарвам елементите от списъка по key, а за value записвам броя на срещанията.
С lambda израз намирам максималната стойност, за кой ключ е и проверявам дали е N/2 + 1 и изписвам на конзолата коя е стойноста, ако удовлетворява изискването.


от AsenVal (3487 точки)


5

Задача 8

Въвеждам масива от числа в List<int>(). В Dictionary<int, int> записвам в Key съответния член от масива, а във Value пазя колко пъти съм срещнал члена. Използвам метода TryGetValue() за който се твърди, че е предпочитан пред стандартния ContainsKey(), http://www.dotnetperls.com/dictionary. Сортирам речника по pair.Value във възходящ ред, т.е. за първи елемент в речника сортирам най-често срещания член от масива, като го проверявам дали той отговаря на изискването да бъде majorant. Няма нужда от проверка на следващи членове, срещани по-рядко, поради правилото majorant >= N/2 +1.

 


от Dimov (907 точки)


0
Защо сортираш речника? Достатъчно е само да намериш ключа с най-голяма стойност и да провериш дали удовлетворява условието за мажорант.

от pirin (1101 точки)

0
Защото при сортиране по стойност, ключът с най-висока стойност се намира на първа позиция. Тъй като условието N/2 + 1 предвижда само една потенциална стойност,то нашият отговор или ще е ключът на първа позиция, или никоя друга. Другото е да напишeм сравнение на всички ключове по стойност и да избера този с по-голяма стойност. Исках да напиша различно решение, пък и да потренирам със сортиранията - може на някой да му е било полезно и интересно :)
P.S. тъй като нямаме директно сортиране на обикновения речник по Values в Dictionary

от Dimov (907 точки)



1

Заповядайте и моето решение на задачата: CLICK. Използвам алгоритъма от книгата "Програмиране = ++Алгоритми;" - Обхождам входния масив и добавям в стека числото, ако то съвпада с най-горното число в стека, в противен случай Pop-вам най-горното число. След това се обхожда масива и се проверява дали най-горния елемент в стека наистина е мажорант или не. 


от vlad_karamfilov (4595 точки)