Java O(n) solution with constant memory


  • 16
    T
    /*
    Moore’s Voting Algorithm
    */
    
    public class Solution {
        public int majorityElement(int[] num) {
            int maj=0;
            int count = 0;
            int n = num.length;
            for (int i = 0; i < n; i++){
                if (count == 0){
                    maj = num[i];
                    count++;
                }
                else if (num[i] == maj){
                    count++;
                    if (count > n/2) return maj;
                }
                else count--;
            }
            return maj;
        }
    }

  • 2
    B

    public class Solution {
    public int majorityElement(int[] num) {
    Arrays.sort(num);
    return num[num.length/2];
    }


  • 0
    S

    Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.


Log in to reply
 

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