169. Majority Element

easy · array · hash-table · divide-and-conquer · sorting · counting · solved 2026.08.01 · 27 sec read

C++

class Solution {public:    int majorityElement(vector<int>& nums) {        int count = 0;        int element = 0;        int limit = nums.size() / 2;        if (nums.size() == 1) return nums[0];        for (int j = 1; j < nums.size(); j *= 2) {            element = nums[j];            count = 0;            for (int i = 0; i < nums.size(); i++) {                if (nums[i] == element) {                    count++;                }                if (count > limit) {                    return element;                }            }        }        element = nums[nums.size() - 1];        count = 0;        for (int i = 0; i < nums.size(); i++) {            if (nums[i] == element) {                count++;            }            if (count > limit) {                return element;            }        }        return element;    }};

kinda cheated my way to 0ms run time with a n log n search. could have just used sort at that point. but should look into moore game theory as that should also work. my understanding so far is that you select one canidate, and go through every single element and if is the canidate, you add one to a count, and if not you subtract. if count is 0 again then replace canidate with that number and algo should work. you need another verify step after doing that.