Java 2ms O(n) solution


  • 20
    F
    public class Solution {
        public int majorityElement(int[] nums) {
            int res = nums[0];
            int count = 1;
        
            for (int num : nums) {
                if (res == num) ++count;
                else --count;
            
                if (count == 0) {
                    res = num;
                    count = 1;
                }
            }
        
            return res;
        }
    }

  • 0
    C

    I don't understand what this "res" stands for.


  • 0
    F

    The "res" represents result. It's majority element of this problem.


  • 0
    C

    'res' actually represents potential majority element in the array. In general, one more pass is required to confirm if 'res' is actually majority element or not. However since in this problem we are told that majority element always exists, we can safely assume 'res' represents majority element.

    In cases where there is no majority element in the array, 'res' would just point to random element in array.

    This solution is based on algorithm called Moore's Voting algorithm.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.