عنصر غالب

این سؤال یکی از جالب‌ترین سؤال های قابل حل با روش استقرایی است که در زیر به بررسی آن در زمان $O(n)$ می‌پردازیم.

آرایه‌ای شامل $n$ عضو داریم. می‌خواهیم عنصری را در آن پیدا کنیم که بیش از $\frac{n}{2}$ بار تکرار شده است.

دو مقدار $x, occ$ را به صورت زیر تعریف کنید:
$x$: عنصری که شانس تکرار بیش از مقدار مورد نظر را داشته باشد.
$occ$: اگر $T$ را برابر با تعداد تکرار‌های $x$ در آرایه در نظر بگیرید، اگر $T \leq \frac{n}{2}$ بود،‌ آن‌گاه $occ \leq T$ است. در غیر این صورت‌ $occ = n - T$ می‌باشد.
حال در صورتی که مقدیر $x, occ$ را در هر مرحله، با حذف عضو $n$ ام، و اضافه کردن آن، به صورت استقرایی انجام دهیم، واضح است که اگر عنصری شرایط ما را برآورده کرده باشد، همان عنصر $x$ خواهد بود. پس کافی است که فقط بررسی کنیم که آیا عنصر $x$ بیش از مقدار مورد نظر ما در آرایه آمده است یا خیر.

پیچیدگی این الگوریتم به وضوح از $O(n)$ است.

dominant_element.cpp

#include <iostream>
using namespace std;
const int maxn = 1000 * 1000 + 10;
int a[maxn];
int main() {
     int n;
     cin >> n;
     for(int i=0;i<n;++i)
         cin >> a[i];
 
     int x = a[0];
     int occ = 1;
     for(int i=1;i<n;++i)
         if(x == a[i])
             occ++;
         else{
             occ--;
             if(occ < 0) {
                 occ = 1;
                 x = a[i];
             }
         }
 
     int T = 0;
     for(int i=0;i<n;++i)
         if(x == a[i])
             T++;
 
     if(T > n / 2)
        cout << "We find it!! The element is: " << x << endl;
     else
        cout << "There is no dominant element :(" << endl;
 
     return 0;
}