Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/169.html

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

 

Follow-up: Could you solve the problem in linear time and in O(1) space?

Algorithm

First of all, there is a prerequisite, there must be a number that appears more than half of the number, then if the counter is reduced to 0, it means that the number of numbers that are not candidates currently is the same as the number of candidates, then this candidate It is already very weak, and it may not appear more than half. At this time, choose to replace the current candidate.

Or, after sorting, mid is always the majority.

Code

  • public class Majority_Element {

    public class Solution {
        public int majorityElement(int[] nums) {
            int res = 0, cnt = 0;
            for (int num : nums) {
                if (cnt == 0) {res = num; ++cnt;}
                else if (num == res) ++cnt;
                else --cnt;
            }
            return res;
        }
    }

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


############

class Solution {
    public int majorityElement(int[] nums) {
        int cnt = 0, m = 0;
        for (int v : nums) {
            if (cnt == 0) {
                m = v;
                cnt = 1;
            } else {
                cnt += (m == v ? 1 : -1);
            }
        }
        return m;
    }
}

  • // OJ: https://leetcode.com/problems/majority-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans = 0, cnt = 0;
        for (int n : nums) {
            if (ans == n) ++cnt;
            else if (cnt > 0) --cnt;
            else {
                ans = n;
                cnt = 1;
            }
        }
        return ans;
    }
};

  • class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = m = 0
        for v in nums:
            if cnt == 0:
                m, cnt = v, 1
            else:
                cnt += 1 if m == v else -1
        return m

############

class Solution(object):
  def majorityElement(self, num):
    return sorted(num)[len(num) / 2]


  • func majorityElement(nums []int) int {
	cnt, m := 0, 0
	for _, v := range nums {
		if cnt == 0 {
			m, cnt = v, 1
		} else {
			if m == v {
				cnt++
			} else {
				cnt--
			}
		}
	}
	return m
}

  • /**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
    let cnt = 0,
        m = 0;
    for (const v of nums) {
        if (cnt == 0) {
            m = v;
            cnt = 1;
        } else {
            cnt += m == v ? 1 : -1;
        }
    }
    return m;
};


  • public class Solution {
    public int MajorityElement(int[] nums) {
        int cnt = 0, m = 0;
        foreach (int v in nums)
        {
            if (cnt == 0)
            {
                m = v;
                cnt = 1;
            }
            else
            {
                cnt += m == v ? 1 : -1;
            }
        }
        return m;
    }
}

  • impl Solution {
    pub fn majority_element(nums: Vec<i32>) -> i32 {
        let mut m = 0;
        let mut cnt = 0;
        for &v in nums.iter() {
            if cnt == 0 {
                m = v;
                cnt = 1;
            } else {
                cnt += if m == v { 1 } else { -1 };
            }
        }
        m
    }
}

  • class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function majorityElement($nums) {
        $major = 0;
        $count = 0;
        for ($i = 0; $i < count($nums); $i++) {
            if ($count == 0) $major = $nums[$i];
            if ($major == $nums[$i]) $count++;
            else $count--;
        }
        return $major;
    }
}

  • function majorityElement(nums: number[]): number {
    let cnt: number = 0;
    let m: number = 0;
    for (const x of nums) {
        if (cnt === 0) {
            m = x;
            cnt = 1;
        } else {
            cnt += m === x ? 1 : -1;
        }
    }
    return m;
}

All Problems

All Solutions