Majority Element Solutions in C++

// Source : https://oj.leetcode.com/problems/majority-element/
// Author : Hao Chen
// Date   : 2014-12-25



#include <stdlib.h>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;


// Moore Voting Algorithm
// Refer to: 
// http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
int majorityElement(vector<int> &num) {
    int majority;
    int cnt = 0;
    for(int i=0; i<num.size(); i++){
        if ( cnt ==0 ){
            majority = num[i];
            cnt++;
        }else{
            majority == num[i] ? cnt++ : cnt --;
            if (cnt > num.size()/2) return majority;
        }
    }
    return majority;

}


vector<int> &split(const string &s, char delim, vector<int> &elems) {
    stringstream ss(s);
    string item;
    while (getline(ss, item, delim)) {
        elems.push_back(atoi(item.c_str()));
    }
    return elems;
}


vector<int> split(const string &s, char delim) {
    vector<int> elems;
    split(s, delim, elems);
    return elems;
}


int main(int argc, char** argv)
{
    //string array = "1,2,1,2,1,2,1,2,1,2,1";
    string array = "2,2,1,1,1";
    if (argc > 1){
        array = argv[1];
    }

    cout << "[" << array << "]" << endl;
    vector<int> num = split(array, ',');
    cout << majorityElement(num) <<endl;

    return 0;
}

/// Source : https://leetcode.com/problems/majority-element/description/
/// Author : liuyubobobo
/// Time   : 2017-11-14

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

/// Sort
/// Time Complexity: O(nlogn)
/// Space Complexity: O(1)
class Solution {

public:
    int majorityElement(vector<int>& nums) {

        assert(nums.size() > 0);

        sort(nums.begin(), nums.end());
        return nums[nums.size()/2];
    }
};

int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/majority-element/description/
/// Author : liuyubobobo
/// Time   : 2017-11-14

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cassert>

using namespace std;

/// Using Hash Map
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int majorityElement(vector<int>& nums) {

        assert(nums.size() > 0);

        unordered_map<int, int> records;
        for(int num: nums)
            records[num] ++;

        for(pair<int, int> record: records)
            if(record.second > nums.size()/2)
                return record.first;

        throw invalid_argument("No Solution!");
    }
};

int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/majority-element/description/
/// Author : liuyubobobo
/// Time   : 2017-11-14

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

/// Using Randomization
/// Time Complexity: Worst: O(infinity)
///                  Average: O(n)
/// Space Complexity: O(1)
class Solution {

public:
    int majorityElement(vector<int>& nums) {

        assert(nums.size() > 0);

        srand(time(NULL));

        // The expectation to run this loop is 2
        // see the proof in https://leetcode.com/problems/majority-element/solution/#approach-4-randomization-accepted
        while(true){
            int randIndex = rand()%nums.size();
            if(occurance(nums, nums[randIndex]) > nums.size()/2)
                return nums[randIndex];
        }
    }

private:
    int occurance(const vector<int>& nums, int target){
        int cnt = 0;
        for(int num: nums)
            if(num == target)
                cnt ++;
        return cnt;
    }
};

int main() {

    int nums[1] = {1};
    vector<int> vec(nums, nums + 1);
    cout << Solution().majorityElement(vec) << endl;
    return 0;
}

/// Source : https://leetcode.com/problems/majority-element/description/
/// Author : liuyubobobo
/// Time   : 2017-11-14

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Divide and Conquer
/// Time Complexity: O(nlogn)
/// Space Complexity: O(lgn) for recursive call
class Solution {

public:
    int majorityElement(vector<int>& nums) {

        assert(nums.size() > 0);

        return majorityElement(nums, 0, nums.size() - 1);
    }

private:
    int majorityElement(const vector<int>& nums, int left, int right){

        int len = right - left + 1;
        if(len <= 2){
            assert(len >= 1);
            return nums[left];
        }

        int mid = (left + right) / 2;
        int leftMajority = majorityElement(nums, left, mid);
        int rightMajority = majorityElement(nums, mid + 1, right);

        if(leftMajority == rightMajority)
            return leftMajority;

        int leftMajorityCnt = occurance(nums, left, mid, leftMajority);
        int rightMajorityCnt = occurance(nums, mid + 1, right, rightMajority);

        assert(leftMajority != rightMajority);
        return leftMajorityCnt > rightMajorityCnt ? leftMajority : rightMajority;
    }

    int occurance(const vector<int>& nums, int l, int r, int target){
        int cnt = 0;
        for(int i = l ; i <= r ; i ++)
            if(nums[i] == target)
                cnt ++;
        return cnt;
    }
};

int main() {

    int nums[1] = {1};
    vector<int> vec(nums, nums + 1);
    cout << Solution().majorityElement(vec) << endl;
    return 0;
}

/// Source : https://leetcode.com/problems/majority-element/description/
/// Author : liuyubobobo
/// Time   : 2017-11-14

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Boyer-Moore Voting Algorithm
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {

public:
    int majorityElement(vector<int>& nums) {

        assert(nums.size() > 0);

        int count = 0;
        int res = -1;
        for(int num: nums){
            if(count == 0)
                res = num;

            count += (res == num) ? 1 : -1;
        }

        return res;
    }
};

int main() {

    int nums[1] = {1};
    vector<int> vec(nums, nums + 1);
    cout << Solution().majorityElement(vec) << endl;
    return 0;
}