Алгоритми | мажоритарен елемент

Опитвам се да напиша алгоритъм, който да връща true, ако мажоритарен елемент съществува в масив, и false в противен случай. редактиране: мога да кажа само дали два елемента са равни. което означава, че не мога да използвам ‹ или >, само =. редактиране: решението трябва да е в метода разделяй и владей. времето за изпълнение не трябва да надхвърля nlogn и аз написах нещо в java, но не съм сигурен дали е правилно и как да изчисля времето за изпълнение... ето какво имам:

public static boolean MajorityBoolean(int[] arr) {
    int c;
    int n = arr.length;
    for (int i = 0; i < n; i = i + 2) {
        System.out.println("*");
        if ((arr[i] == arr[(i + 1)%n]) || ((arr[i] == arr[(i - 1+n)%n]))) {
            c = 0;
            for (int j = 0; j < n; j = j + 1)
                if (arr[j] == arr[i])
                    c = c + 1;
            if (c > n / 2)
                return true;
        }
    }
    return false;
}

element runtime algorithm
person shachar0n    schedule 14.04.2012    source източник
comment
Добавих таг за домашна работа, тъй като изглежда е така. Ако греша, моля поправете ме.   -  person amit    schedule 14.04.2012
comment
възможен дубликат на Намиране на мажоритарен елемент в масив   -  person erickson    schedule 14.04.2012
comment
По-конкретно, това е най-доброто решение на дублиращия се въпрос.   -  person erickson    schedule 14.04.2012

Отговори (3)


arrow_upward
5
arrow_downward

Времето на изпълнение на описания алгоритъм е O(n^2). Външният цикъл се изпълнява n/2 пъти, като по този начин вътрешният брояч j се нулира n/2 пъти и по този начин вътрешният цикъл се изпълнява общо O(n^2) пъти.

Не съм сигурен, че следвам логиката зад вашата идея, но ето два подхода как бих я приложил [в псевдокод на високо ниво]:

(1) създайте хистограма от данните:

  • създайте Map<Integer,Integer> [ключът е елементът и стойността е броят на срещанията]
  • итерирайте масива и за всеки елемент пребройте колко пъти се появява
  • повторете хистограмата и намерете дали има уникален максимум.
  • Ако има - връща true, иначе връща false.

Този подход е средно O(n), ако използвате HashMap като картата.

(2) сортиране и намиране на макс.

Това решение е O(nlogn) среден + най-лошият случай [всъщност, в зависимост от сортирането - сливане sort ви дава O(nlogn) най-лошия случай, докато бързото сортиране ви дава O(n^2) най-лошия случай, като и двата са O(nlogn) средния случай ].

РЕДАКТИРАНЕ:

Разбрах погрешно проблема, мислех, че търсите дали има уникален максимум. Тези 2 решения все още са подходящи за проблема, просто трябва да промените последната стъпка на всяко [за да проверите дали най-често срещаният елемент се появява повече от половината пъти, което отново е сравнително лесно и изпълнимо в O(n)].

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

person amit    schedule 14.04.2012
comment
първо, благодаря за помощта! второ, идеята ми беше, че във всеки масив, който има мажоритарен елемент, трябва да има две еднакви числа едно след друго (като се има предвид, че масивът е нещо като кръг, така че последният елемент е близо до първия). това добра\правилна идея ли е? между другото, очевидно трябваше да напиша алгоритъма в метод разделяне-н-владеене, така че моят не е добър (също така времето му за изпълнение е O(n²), което е повече от )(nlogn)). - person shachar0n; 14.04.2012
comment
@shachar0n: (1) Все още не следвам логиката, защо масивът е кръгъл? :\. (2) Неразбрах въпроса, мислех, че търсите дали има уникален максимум. Тези две решения все още отговарят на разглеждания проблем, с лека модификация в последната стъпка на всяко решение. (3) Въпросът, който описвате, може да бъде разрешен с помощта на алгоритъм за избор. Намерете медианата - и след това вижте дали е мажоритарният елемент. Алгоритъмът за избор всъщност е решение "разделяй и владей". - person amit; 14.04.2012
comment
(1) това, което имах предвид, беше, че ако един масив има мажоритарен елемент, той трябва да има два близки елемента, които са еднакви. ако масивът е като този: 1010101, тогава последният и първият елемент са еднакви - и това имам предвид, като третирам масива като кръг (използвайки модул %). (2)(3) забравих да спомена още едно ограничение: мога да знам само дали два елемента са еднакви, но не мога да разбера дали единият е по-голям или по-малък от другия, което означава, че мога да използвам само = и не мога да използвам : › ‹. - person shachar0n; 14.04.2012

arrow_upward
1
arrow_downward

Мажоритарен елемент в масив A[] с размер n е елемент, който се появява повече от n/2 пъти

public static boolean find(int[] arr, int size) { 
int count = 0, i, mElement;
for (i = 0; i < size; i++) {
    if (count == 0)
        mElement = arr[i];
    if (arr[i] == mElement) 
        count++;
    else
        count--;
}
count = 0;
for (i = 0; i < size; i++)
    if (arr[i] == mElement)
        count++;
if (count > size/2)
    return true;
return false;
}
person coder101    schedule 17.02.2015

arrow_upward
0
arrow_downward

Следва O(n) решение Намиране на мнозинство елемент

person MoveFast    schedule 14.04.2012
comment
Това сочи към добро решение, но трябва да гласувате за затваряне на дублиращите се въпроси, ако можете, или просто да направите коментар по въпроса, ако не можете. - person erickson; 14.04.2012