Share my divide&conquer approach(nlgn)


  • 1
    I
    public class Solution {
    public int majorityElement(int[] num) {
        if(num.length == 1) return num[0];
        int[] rst = new int[1];
        getMajority(num, 0, num.length-1, rst);
        return rst[0];
    }
    
    public void getMajority(int[] num, int l, int r, int[] rst){
        if(l >= r){
            rst[0] = num[r];
            return;
        }
        int m = r - (r-l)/2;
        // check if num[m] is majority element in num
        int count = 0;
        for(int i = 0; i < num.length; i++){
            if(num[i] == num[m])
                count++;
        }
        if(count > num.length/2){
            rst[0] = num[m];
            return;
        }
        getMajority(num, l, m-1, rst);
        getMajority(num, m+1, r, rst);
    }
    

    }

    time & space complexity: nlgn. O(n) solution seems hard to come up during an interview.


  • 0
    M

    Is this divide and conquer? This seems to me more like "randomization" in which you pick the middle element and see if it is the majority element.


  • 0
    E

    I agree with you.


Log in to reply
 

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