Leetcode # 169, 229 Majority Element I and II

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.

这一题可以用排序之后查看序列正中间那个元素的方法来解。但是复杂度是排序的复杂度nlog(n)。用如下的方法借鉴Moore Voting。

class Solution(object):

    def majorityElement(self, nums):

        """

        :type nums: List[int]

        :rtype: int

        """

        major = 0

        count = 0

        for x in nums:

            if count == 0:

                major = x

                count = 1

            elif x == major:

                count += 1

            else:

                count -= 1

        return major

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

这一题由于对复杂度的限制是线性的，所以不能用排序。可以使用两个majority的candadite。

class Solution(object):

    def majorityElement(self, nums):

        """

        :type nums: List[int]

        :rtype: List[int]

        """

        if not nums:

            return []

        n1, n2, c1, c2 = 0, 1, 0, 0 

        for num in nums:

            if num == n1:

                c1 += 1

            elif num == n2:

                c2 += 1

            elif c1 == 0:

                n1 = num; c1 = 1

            elif c2 == 0:

                n2 = num; c2 = 1

            else:

                c1 -= 1; c2 -= 1

        size = len(nums)

        return [n for n in (n1, n2) if nums.count(n) > size/3]

巴特西

Leetcode # 169, 229 Majority Element I and II

最新文章

热门文章