Would anybody mind explaining this Divide and Conquer to me ? What is really going on here ? Thanks


  • 0
    C

    This method was proposed by someone to find majority element in the array.I can't really understand how things are going on.Can anyone explain this to me.

    Regards.


  • 1
    M

    Let f(i, j) be the majority of elements from i-th to j-th in nums

    By the definition of majority it is the number of elements that appears more than half of the total numbers in the array,

    • f(i, mid) appears more than (mid - i+1)/2 times from i-th to mid-th in nums
    • f(mid+1, j) appears more than (j - mid)/2 times from (mid+1)-th to j-th in nums

    Assume that all the rest elements in nums from i-th to j-th except those two numbers above are the same,
    then they will appear less than (mid-i+1)/2 + (j-mid)/2 = (j-i+1)/2 times from i-th to j-th in nums

    Therefore any elements except those two numbers above cannot be the majority of elements in nums;
    hence f(i,j) = f(i,mid) or f(mid+1,j)


  • 0
    W

    Then what's next? how to make the decision between f(i,mid) and f(mid+1,j)


Log in to reply
 

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