Topic describes

Find a number that occurs more than half the length of the array.

You can assume that the array is non-empty and that a given array always has most elements.

Example 1:

Input: [1, 2, 3, 2, 2, 2, 5, 4, 2] Output: 2Copy the code

Limitations:

  • 1 <= Array length <= 50000

solution

Moore voting. Time complexity O(n), space complexity O(1).

Python3

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = major = 0
        for num in nums:
            if cnt == 0:
                major = num
                cnt = 1
            else:
                cnt += (1 if major == num else -1)
        return major
Copy the code

Java

class Solution { public int majorityElement(int[] nums) { int cnt = 0, major = 0; for (int num : nums) { if (cnt == 0) { major = num; cnt = 1; } else { cnt += (major == num ? 1:1); } } return major; }}Copy the code

JavaScript

/** * @param {number[]} nums * @return {number} */ var majorityElement = function(nums) { let cnt = 0; let major = 0; for (const num of nums) { if (cnt == 0) { major = num; cnt = 1; } else { cnt += (major == num ? 1:1); } } return major; };Copy the code

C++

class Solution { public: int majorityElement(vector<int>& nums) { int votes = 0, x = 0; for (int num : nums) { if (votes == 0) x = num; votes += x == num ? 1:1; } return x; }};Copy the code