Əsas element (Həll təhlili)

Alqoritm Analizi

$x$ əksəriyyət elementi olsun. Giriş rəqəmlərini emal etməyə başlayacağıq. $x$-ə bərabər olan hər rəqəm bir yığın üzərinə yerləşdiriləcək. $x$-ə bərabər olmayan bir rəqəm aldıqda, yığından bir rəqəm çıxarılacaq. Beləliklə, məlumatların emalının sonunda, yığının üstündə əksəriyyət elementi olacaq.

Əvvəlcə, yığını təmizləyəcəyik. Növbəti element $a$-nı emal edərkən:

• əgər yığın boşdursa, onda push(a);

• əgər yığının üstündə $a$ rəqəmi varsa, onda push(a);

• əgər yığının üstündə $a$-dan fərqli bir rəqəm varsa, onda pop().

Bütün rəqəmlər emal edildikdən sonra, yığının üstündə $x$ rəqəmi varsa (əgər yığın boşdursa, əksəriyyət yoxdur), onun əksəriyyət elementi olub olmadığını yoxlamaq lazımdır. Bunun üçün, başlanğıc rəqəmlər toplusunda $x$ rəqəminin neçə dəfə göründüyünü sayın. Əgər $x$ \frac{n}{2} dəfədən çox görünürsə, cavab müsbətdir.

Yığında hər zaman bir rəqəm olduğundan (mümkündür ki, bir neçə dəfə), yığını iki dəyişənlə model edəcəyik:

• $maj$ – yığında olan rəqəm;

• $cnt$ – yığında olan $maj$ rəqəminin sayı;

Nümunə

Birinci nümunəni nəzərdən keçirək. Alqoritmin sonunda, yığında 3 var. Gəlin bunun əksəriyyət elementi olub olmadığını yoxlayaq. Bunun üçün, başlanğıc massivdə 3 rəqəminin neçə dəfə göründüyünü sayın. 3 rəqəmi n = 7 uzunluğunda bir massivdə 4 dəfə görünür. Çünki 4 > \frac{n}{2}, 3 rəqəmi əksəriyyət elementidir.

Alqoritmin Tətbiqi

Giriş rəqəmlər ardıcıllığını bir massivdə m-də saxlayacağıq.

int m[110];

Yığını model etmək üçün maj və cnt dəyişənlərini elan edin:

• maj – yığında olan rəqəm;

• cnt – yığında olan maj rəqəminin sayı;

int maj, cnt;

Giriş məlumatlarını oxuyun.

scanf("%d",&n);
for(int i = 0; i < n; i++)
    scanf("%d",&m[i]);

İlk olaraq, yığını boş olaraq qurun.

maj = 0; cnt = 0;

Giriş rəqəmlərini emal edərək, yığının əməliyyatını simulyasiya edin.

for(int i = 0; i < n; i++) {
    if (cnt == 0) {maj = m[i]; cnt++;}
    else if (m[i] == maj) cnt++;
    else cnt--;
}

cnt dəyişənində, m massivində maj rəqəminin neçə dəfə göründüyünü sayın.

cnt = 0;
for(int i = 0; i < n; i++)
    if (m[i] == maj) cnt++;

Əgər 2 * cnt > n olarsa, əksəriyyət mövcuddur. Əks halda, yox (res -1 olaraq təyin ediləcək).

if(2 * cnt > n) res = maj; else res = -1;

Cavabı çap edin.

printf("%d\n",res);

Java Tətbiqi

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m[] = new int[n];
        for(int i = 0; i < n; i++)
            m[i] = sc.nextInt();
        int maj = 0, cnt = 0;
        for(int i = 0; i < n; i++) {
            if (cnt == 0) {maj = m[i]; cnt++;}
            else if (m[i] == maj) cnt++;
            else cnt--;
        }
        cnt = 0;
        int res;
        for(int i = 0; i < n; i++)
            if (m[i] == maj) cnt++;
        if(2 * cnt > n) res = maj; else res = -1;
        System.out.println(res);
    }
}

Python Tətbiqi

n = int(input())
m = list(map(int, input().split()))

maj = 0
cnt = 0

for num in m:
    if cnt == 0:
        maj = num
        cnt += 1
    elif num == maj:
        cnt += 1
    else:
        cnt -= 1

cnt = 0
for num in m:
    if num == maj: cnt += 1

if 2 * cnt > n: res = maj
else: res = -1

print(res)