LeetCode 169 - Majority Number I

Related: LeetCode 229 + LintCode: Majority Number II
https://leetcode.com/problems/majority-element

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 exist in the array.

X. Boyer-Moore Voting Algorithm
https://leetcode.com/problems/majority-element/discuss/51828/C%2B%2B-solution-using-Moore's-voting-algorithm-O(n)-runtime-comlexity-an-no-extra-array-or-hash-table
Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element. Below code loops through each element and maintains a count of the element that has the potential of being the majority element. If next element is same then increments the count, otherwise decrements the count. If the count reaches 0 then update the potential index to the current element and sets count to 1.

int majorityElement(vector<int> &num) {
    int majorityIndex = 0;
    for (int count = 1, i = 1; i < num.size(); i++) {
        num[majorityIndex] == num[i] ? count++ : count--;
        if (count == 0) {
            majorityIndex = i;
            count = 1;
        }
    }
        
    return num[majorityIndex];
}

https://discuss.leetcode.com/topic/8692/o-n-time-o-1-space-fastest-solution

You need(may) check if "major" is really a majority element.

    public int majorityElement(int[] num) {

        int major=num[0], count = 1;
        for(int i=1; i<num.length;i++){
            if(count==0){
                count++;
                major=num[i];
            }else if(major==num[i]){
                count++;
            }else count--;
            
        }
        return major;
    }

X. Quick Select

    int majorityElement(vector<int>& nums) {

        nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());

        return nums[nums.size() / 2];

    }

X. 

public int majorityElement1(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
}

// Hashtable 
public int majorityElement2(int[] nums) {
    Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();
    //Hashtable<Integer, Integer> myMap = new Hashtable<Integer, Integer>();
    int ret=0;
    for (int num: nums) {
        if (!myMap.containsKey(num))
            myMap.put(num, 1);
        else
            myMap.put(num, myMap.get(num)+1);
        if (myMap.get(num)>nums.length/2) {
            ret = num;
            break;
        }
    }
    return ret;
}

// Moore voting algorithm
public int majorityElement3(int[] nums) {
    int count=0, ret = 0;
    for (int num: nums) {
        if (count==0)
            ret = num;
        if (num!=ret)
            count--;
        else
            count++;
    }
    return ret;
}

X. 32n Bit Manipulation
https://leetcode.com/problems/majority-element/discuss/51649/Share-my-solution-Java-Count-bits

We can iterate over the bits of all numbers and for every position find out if ones outnumber the zeros (among all numbers). If this is the case, the corresponding bit of the ret variable (which holds the result) is set. We essentially "construct" the number we look for.

public int majorityElement(int[] num) {

    int ret = 0;

    for (int i = 0; i < 32; i++) {

        int ones = 0, zeros = 0;

        for (int j = 0; j < num.length; j++) {
            if ((num[j] & (1 << i)) != 0) {
                ++ones;
            }
            else
                ++zeros;
        }

        if (ones > zeros)
            ret |= (1 << i);
    }
    
    return ret;
}

The key lies in how to count the number of 1's on a specific bit. Specifically, you need a mask with a 1 on the i-the bit and 0 otherwise to get the i-th bit of each element in nums. The code is as follows.

public int majorityElement(int[] nums) {
    int[] bit = new int[32];
    for (int num: nums)
        for (int i=0; i<32; i++) 
            if ((num>>(31-i) & 1) == 1)
                bit[i]++;
    int ret=0;
    for (int i=0; i<32; i++) {
        bit[i]=bit[i]>nums.length/2?1:0;
        ret += bit[i]*(1<<(31-i));
    }
    return ret;
}

https://discuss.leetcode.com/topic/17446/6-suggested-solutions-in-c-with-explanations

Randomization

Because more than $\lfloor \dfrac{n}{2} \rfloor$ array indices are occupied by the majority element, a random array index is likely to contain the majority element.

This is a really nice idea and works pretty well (16ms running time on the OJ, almost fastest among the C++ solutions). The proof is already given in the suggested solutions.

The code is as follows, randomly pick an element and see if it is the majority one.

    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        srand(unsigned(time(NULL)));
        while (true) {
            int idx = rand() % n;
            int candidate = nums[idx];
            int counts = 0; 
            for (int i = 0; i < n; i++)
                if (nums[i] == candidate)
                    counts++; 
            if (counts > n / 2) return candidate;
        }
    }

X. Divide and Conquer

https://zxi.mytechroad.com/blog/divide-and-conquer/leetcode-169-majority-element/

    int majorityElement(vector<int>& nums) {

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

    }

private:

    pair<int, int> majorityElement(const vector<int>& nums, int l, int r) {

        if (l == r) return {nums[l], 1};

        int mid = l + (r - l) / 2;

        auto ml = majorityElement(nums, l, mid);

        auto mr = majorityElement(nums, mid + 1, r);

        if (ml.first == mr.first) return { ml.first, ml.second + mr.second };

        if (ml.second > mr.second)

            return { ml.first, ml.second + count(nums.begin() + mid + 1, nums.begin() + r + 1, ml.first) };

        else

            return { mr.first, mr.second + count(nums.begin() + l, nums.begin() + mid + 1, mr.first) };

    }

    int majorityElement(vector<int>& nums) {

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

    }

private:

    int majorityElement(const vector<int>& nums, int l, int r) {

        if (l == r) return nums[l];

        const int m = l + (r - l) / 2;

        const int ml = majorityElement(nums, l, m);

        const int mr = majorityElement(nums, m + 1, r);

        if (ml == mr) return ml;

        return count(nums.begin() + l, nums.begin() + r + 1, ml) >

               count(nums.begin() + l, nums.begin() + r + 1, mr)

               ? ml : mr;

    }

https://leetcode.com/articles/majority-element/

If we know the majority element in the left and right halves of an array, we can determine which is the global majority element in linear time.

Here, we apply a classical divide & conquer approach that recurses on the left and right halves of an array until an answer can be trivially achieved for a length-1 array. Note that because actually passing copies of subarrays costs time and space, we instead pass lo and hi indices that describe the relevant slice of the overall array. In this case, the majority element for a length-1 slice is trivially its only element, so the recursion stops there. If the current slice is longer than length-1, we must combine the answers for the slice's left and right halves. If they agree on the majority element, then the majority element for the overall slice is obviously the same1. If they disagree, only one of them can be "right", so we need to count the occurrences of the left and right majority elements to determine which subslice's answer is globally correct. The overall answer for the array is thus the majority element between indices 0 and $n$

• Time complexity : $O(nlgn)$
  Each recursive call to majority_element_rec performs two recursive calls on subslices of size $\frac{n}{2}$ and two linear scans of length $n$. Therefore, the time complexity of the divide & conquer approach can be represented by the following recurrence relation:
  $T(n) = 2T(\frac{n}{2}) + 2n$
  
  
  By the master theorem, the recurrence satisfies case 2, so the complexity can be analyzed as such:
  $\begin{aligned} T(n) &amp;= \Theta(n^{log_{b}a}\log n) \\ &amp;= \Theta(n^{log_{2}2}\log n) \\ &amp;= \Theta(n \log n) \\ \end{aligned}$

  private int countInRange(int[] nums, int num, int lo, int hi) {

    int count = 0;

    for (int i = lo; i <= hi; i++) {

      if (nums[i] == num) {

        count++;

      }

    }

    return count;

  }

  private int majorityElementRec(int[] nums, int lo, int hi) {

    // base case; the only element in an array of size 1 is the majority

    // element.

    if (lo == hi) {

      return nums[lo];

    }

    // recurse on left and right halves of this slice.

    int mid = (hi - lo) / 2 + lo;

    int left = majorityElementRec(nums, lo, mid);

    int right = majorityElementRec(nums, mid + 1, hi);

    // if the two halves agree on the majority element, return it.

    if (left == right) {

      return left;

    }

    // otherwise, count each element and return the "winner".

    int leftCount = countInRange(nums, left, lo, hi);

    int rightCount = countInRange(nums, right, lo, hi);

    return leftCount > rightCount ? left : right;

  }

  public int majorityElement(int[] nums) {

    return majorityElementRec(nums, 0, nums.length - 1);

  }

This idea is very algorithmic. However, the implementation of it requires some careful thought about the base cases of the recursion. The base case is that when the array has only one element, then it is the majority one.

    int majorityElement(vector<int>& nums) {
        return majority(nums, 0, nums.size() - 1);
    }
private:
    int majority(vector<int>& nums, int left, int right) {
        if (left == right) return nums[left];
        int mid = left + ((right - left) >> 1);
        int lm = majority(nums, left, mid);
        int rm = majority(nums, mid + 1, right);
        if (lm == rm) return lm;
        return count(nums.begin() + left, nums.begin() + right + 1, lm) > count(nums.begin() + left, nums.begin() + right + 1, rm) ? lm : rm;
    }

X. Bit counting
https://discuss.leetcode.com/topic/6286/share-my-solution-java-count-bits
We can iterate over the bits of all numbers and for every position find out if ones outnumber the zeros (among all numbers). If this is the case, the corresponding bit of the ret variable (which holds the result) is set. We essentially "construct" the number we look for.

public int majorityElement(int[] num) {

    int ret = 0;

    for (int i = 0; i < 32; i++) {

        int ones = 0, zeros = 0;

        for (int j = 0; j < num.length; j++) {
            if ((num[j] & (1 << i)) != 0) {
                ++ones;
            }
            else
                ++zeros;
        }

        if (ones > zeros)
            ret |= (1 << i);
    }
    
    return ret;
}

    int majorityElement(vector<int>& nums) {
        int major = 0, n = nums.size();
        for (int i = 0, mask = 1; i < 32; i++, mask <<= 1) {
            int bitCounts = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] & mask) bitCounts++;
                if (bitCounts > n / 2) {
                    major |= mask;
                    break;
                }
            }
        } 
        return major;
    } 

    public int majorityElement(int[] nums) {
        int majorityCount = nums.length/2;

        for (int num : nums) {
            int count = 0;
            for (int elem : nums) {
                if (elem == num) {
                    count += 1;
                }
            }

            if (count > majorityCount) {
                return num;
            }

        }

        return -1; 
    }