Leetcode Study Day 4

Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3
Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2
 

Constraints:

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

My solution

Sort the array

We sort the array first in the non-decreasing order.

sort(nums.begin(), nums.end(), [](int & a, int & b){
            return a < b ;
        });

Count the number of each element

Then we loop the array and count how many times one value appears in the array. As the array is sorted already, we just need to check whether the current element is equal to the previous one. If they are equal, we plus 1 to the count, otherwise, we set the count to 0. We also set one variable to store the best count, and another variable to store the value that has the best count. During the loop, we update the best count and the value that has most count.

for (int i = 1; i < nums.size(); i++){
           if (nums[i] == nums[i-1]){
               count ++;
           } 
           else{
               count = 0;
           }
           if (count > best_count){
               best_count = count;
               return_val = nums[i];
           }
       }

Full code

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int best_count = 0;
        int return_val = 0;
        sort(nums.begin(), nums.end(), [](int & a, int & b){
            return a < b ;
        });
        if (nums.size() == 1){
            return nums[0];
        }
        for (int i = 1; i < nums.size(); i++){
            if (nums[i] == nums[i-1]){
                count ++;
            } 
            else{
                count = 0;
            }
            if (count > best_count){
                best_count = count;
                return_val = nums[i];
            }
        }
        return return_val;
    }
};

Improved Solution

ChatGPT provides a better solution:

You can solve this problem in linear time and O(1) space using a well-known algorithm called “Boyer-Moore Majority Vote Algorithm.” This algorithm allows you to find the majority element in an array efficiently.

Here’s the algorithm in C++:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = nums[0]; // Initialize the candidate as the first element
        int count = 1; // Initialize the count of the candidate element

        for (int i = 1; i < nums.size(); i++) {
            if (count == 0) {
                candidate = nums[i]; // Update the candidate if count becomes 0
                count = 1;
            } else if (nums[i] == candidate) {
                count++; // Increment count if the current element is the same as the candidate
            } else {
                count--; // Decrement count if the current element is different from the candidate
            }
        }

        return candidate; // The candidate is the majority element
    }
};

Compare to my solution, this solution doesn’t sort the array, which save a lot of time. Also, it only have two variables. If the count is not equal to zero, which means the candidate variable is still the majority value. If the count is equal to zero, which means the candidate variable is not the majority value, we update the candidate variable to the current element, and set the count to 1.