Share my divide&conquer approach(nlgn)

  • 1
    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];
        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])
        if(count > num.length/2){
            rst[0] = num[m];
        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

    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

    I agree with you.

Log in to reply

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