1. Use memory :

In the question, it already stated that there must be a majority element. So discard empty situation.

Also it needs the number, not the index.

1 class Solution { 2 public: 3     int majorityElement(vector
     
       &num) { 4         int len = num.size(), result = 0 ,rec = 0; 5         unordered_map
      
        list; 6         for (int i = 0; i < len; i++) { 7             if (list[num[i]]) list[num[i]]++; 8             else list[num[i]] = 1; 9             if (rec < list[num[i]]) {10                 rec = list[num[i]];11                 result = num[i];12             }13         }14         return result;15     }16 };
      
     

 

2. With out memory:

Notes:

1. initialize the record after sorting. Because the ordering has been changed.

2. As question mentioned, majority over (n/2) times. Just use len/2 as the condition.

3. Return value is num[i-1] not num[i]. Because the num[i] is not the current value. Also we can put return current;

1 class Solution { 2 public: 3     int majorityElement(vector
     
       &num) { 4         sort(num.begin(), num.end()); 5         int len = num.size(), rec = 1, current = num[0]; 6         for (int i = 1; i < len; i++) { 7            if (current != num[i]) { 8                if (rec > len/2) { 9                    return num[i-1];10                }11                current = num[i];12                rec = 1;13            } else {14                rec++;15            }16         }17         return num[len-1];18     }19 };