Majority Element

Majority Element

 Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

----------------------------------------- thinking ---------------------------------------------------------------

The odd part of this question is the majority elements is more than [n/2] times, this means that after deleting each unequal pair, there are still some or at least one element left, and this one is the majority one. 

The the question becomes how to discard the unequal pairs.

--------------------------------------- bugs -----------------------------------------------------------------------

starting the index of i and j 

the updating of i is each two steps, which is obvious

the updating of j should be each single step! or bug is introduced because if there are duplicate between i and j, j cannot jump two steps

--------------------------------------- codes -------------------------------------------------------------------------

class Solution {

public:

    int majorityElement(vector<int> &num) {

        int i = 0;

        int j = 1;

        while (j < num.size()) {

            if (num[i] != num[j]) {

                if (j > i + 1) {

                    int tmp = num[i+1];

                    num[i+1] = num[j];

                    num[j] = tmp;

                }

                i += 2;

            } 

            j++;

            

        }

        return num[num.size() - 1];

    }

};