Divide and Conquer?


  • 6
    M

    I have problem coming up with the divide and conquer solution.Assume the base case contains only one element, which is the majority element for the base case. Now suppose we have two elements, each one returning from the base case. Say they are 1 2. There is clearly no majority element in this two-element array. If the whole input array is 1 2 2 and you divide the problem into 1 2 and 2. Of course you pick 2 in the right half. But what to pick in the left half?


  • 5
    W

    I got the idea from: http://www.ece.northwestern.edu/~dda902/336/hw4-sol.pdf. Logically, you always comparing two elements at a time. And if I remember correctly, it's the Tournament Tree mentioned in the CLRS book in the divide and conquer section.

    Since it's guaranteed to have a major element, we can use NULL to represent NO-MAJORITY-ELEMENT in the solution. The tricky part is GetFrequency() makes sure that there is one major element in the two selected element.

    For example:

    (1) In your case 1 2 2, the first 1 2 will return null (and GetFrequency() still cannot decide which one is the major element), and we can just return the 3rd number which is 2.

    (2) In case 1 1 2, the first 1 1 will return 1, and once it compares with 2, the GetFrequency() help us to find 1 is the major element from num[0] to num[2].


  • 0
    M

    This is such a nice divide and conquer solution! Thank you. I will post my implementation of this idea in the following post.


  • 1
    M

    As this question has been answered by Wilbert I will simply post my implementation here. The idea is base on the link Wilbert gives in his answer. To handle the case I use Wilbert's suggestion but modified a bit. That is, for the case that you cannot decide a majority element, the argument "found" will be set to false. "found" will be set to true if a majority element is found. After this all else is just divide and conquer.

    public:
    int majorityElement(vector<int> &num) {
        bool found;
        int result = dac(num,0,num.size()-1,found);
        return result;
    }
    
    private:
    int dac(const vector<int>& num, int l, int r, bool& found) {
        if(l==r) {found=true; return num[l];} // one elem subarray
        
        int m = l+(r-l)/2;
        // find majority elem in the left subarray
        bool foundL;
        int A = dac(num,l,m,foundL);
        // find the majority elem in the right subarray
        bool foundR;
        int B = dac(num,m+1,r,foundR);
        
        // if the majority elem in both sides are the same
        if(foundL && foundR && A == B) {found=true; return A;}
        
        int half = (r-l+1)/2; 
        // check the whole array num[l:r] if A is the majority elem
        if(foundL) {
            if(getFreq(num,l,r,A) > half) {found=true; return A;}
        }
        // check the whole array num[l:r] if B is the majority elem
        if(foundR) {
            if(getFreq(num,l,r,B) > half) {found=true; return B;}
        }
        
        found=false; return 0;
        
    }
    
    int getFreq(const vector<int>& num, int l, int r, int target) {
        int n = 0;
        for(int i=l; i<=r; i++) {
            if(num[i] == target) n++;
        }
        return n;
        
    }
    

    };


  • 0
    T

    another divide-and-conquer solution. not nice
    suppose each intager has 32 bits, I do it in 32 steps from right to left. in each step, i remove the not-majority elements using bitmask. bitNum[i] being 3 means num[i] has been removed.

    int majorityElement(int num[], int n) {
        	int  bitmask = 1;
        	short *bitNum = (short*)malloc(n*sizeof(short));
        	for (int i = 0; i < n; i++)
        		bitNum[i] = 1;
        	int num1 = 0;
        	while (bitmask!=0)
        	{
        		num1 = 0;
        		for (int i = 0; i < n; i++)
        		{
        			if(bitNum[i] < 2)
        			{
        				bitNum[i] = (num[i] & bitmask) ? 1 : 0;
        				num1 += bitNum[i];
        			}
        		}
        		
        		if(num1 > n/2)
        			for (int i = 0; i < n; i++)
        				bitNum[i] = (bitNum[i] == 1)? 1: 3;
        		else
        			for (int i = 0; i < n; i++)
        				bitNum[i] = (bitNum[i] == 0) ? 1 : 3;
        		bitmask <<= 1;
        	}
        	num1 = 0;
        	while (bitNum[num1]!=1)
        		num1++;
        	return num[num1];
        }

Log in to reply
 

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