سوال 150

عنوان سوال : Majority Element

• آسان
• تقسیم و غلبه
• هش تیبل
• شمارش

---

یک آرایه به نام nums به اندازه n داده شده است. مقدار بازگشتی باید «عنصر غالب» باشد.
عنصر غالب عنصری است که بیش از ⌊n / 2⌋ بار در آرایه ظاهر می‌شود.
می‌توانید فرض کنید که در آرایه همیشه یک عنصر غالب وجود دارد.

مثال ۱:
ورودی: nums = [3,2,3]
خروجی: 3

مثال ۲:
ورودی: nums = [2,2,1,1,1,2,2]
خروجی: 2

محدودیت‌ها:
n == nums.length
1 <= n <= 5 * 10⁴
-10⁹ <= nums[i] <= 10⁹
فرض بر این است که برای ورودی تولیدشده، همیشه یک عنصر غالب در آرایه وجود خواهد داشت.

راه حل

public class Solution {
    public int MajorityElement(int[] nums) {
        var majority = nums[0];
        var happened = 1;

        for(var i=1;i<nums.Length;i++) {
            if(nums[i] == majority){
                happened++;
            }
            else if (happened==0) {
                majority = nums[i];
                happened = 1;
            }
            else{
                happened--;
            }
        }

        return majority;
    }
}