Question

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

 169. 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.

 Example 1:

 Input: [3,2,3]
 Output: 3

 Example 2:

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

 @tag-array

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

Java

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];
        }
    }
}

// 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]

169 - Majority Element

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions