WEEK#15 Divide and Conquer_Major

Description of the Problem

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exists in the array.

Brute Force

Traverse the array and count the number of times that each entry appears, and find the one that appears more than n/2 times

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //FindMaj(nums, 0, 0 + nums.size() / 2, 0 + nums.size() - 1, nums.size());
        map<int, int> map;
        for (int i = 0; i < nums.size(); i++) {
            std::map<int, int>::iterator it;
            it = map.find(nums[i]);
            if (it != map.end()) {
                it->second++;
            }
            else {
                map.insert(it, std::pair<int, int>(nums[i], 1));
            }
        }
        for (std::map<int,int>::iterator it = map.begin(); it != map.end(); it++) {
            if (it->second > nums.size() / 2)
                return it->first;
        }
    }
    
};

Divide and Conquer

1.Thinking process

An array of size n.
Find an element that appears more than n/2 times.

An array of size n/2.
Find an element that appears more than n/4 times.
.
.
.
An array of size 4.
Find an element that appears more than 4/2 = 2 times.

An array of size 2.
Find an element that appears more than 2/2 = 1 times.

Note that in this way, we can work out no solution...

2. Another way

Divide the array into two halves, and find their majority element independently, until the array is of size 1, in which case the majority element is the one and only entry.
When it comes to considering which majority would it be when two divided arrays are put together, ways are as follows:
// suppose that the majority element of the left array is LM and of the right array, RM

1. if (RM == LM)
   M = LM;
2. if (RM != LM)
   Count the times LM and RM appear in the left/right array, whichever appears more may be the majority element of the merged array.

    int FindMaj(vector<int>& nums, int begin, int mid, int end, int size) {
        if (begin == end)
            return nums[begin];
        int LM = FindMaj(nums, begin, begin + size / 4, begin + size / 2 - 1, size / 2);
        int RM = FindMaj(nums, mid, mid + size / 4, mid + size / 2 - 1, size / 2);
        if (LM == RM)
            return LM;
        else 
            return count(nums.begin()+begin, nums.begin() + mid - 1, LM) > count(nums.begin()+mid, nums.begin() + end, RM) ? LM : RM;
    }

Moore Voting Algorithm

copied from https://leetcode.com/problems/majority-element/discuss/

    int majorityElement(vector<int>& nums) {
        int major, counts = 0, n = nums.size();
        for (int i = 0; i < n; i++) {
            if (!counts) {
                major = nums[i];
                counts = 1;
            }
            else counts += (nums[i] == major) ? 1 : -1;
        }
        return major;
    }

Traverse the array, during which maintain entries of 'major' and 'count', which is potentially the majority element of the array.
The way of maintaining it :
if 'count' equals zero, meaning that there is currently no majority element, so we choose the traversed element as 'major'.
Each time an element E is traversed, if E equals to 'major', count++,
otherwise count--. In this way, when the whole array is traversed, the 'major' that made it to the end would be the entry that appears more than n/2 times in the array.