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.

需要注意的是：这道题只是要找出多数元素，已经默认存在多数元素了，而不需要去判断是否存在多数元素。之前的思路就一直卡在怎么判断多数元素存的的问题上了。

思路解析：

1. 初始化majorityIndex，并且维护其对应count；

2. 遍历数组，如果下一个元素和当前候选元素相同，count加1，否则count减1；

3. 如果count为0时，则更改候选元素，并且重置count为1；

4. 返回A[majorityIndex]

原理：如果majority元素存在（majority元素个数大于n/2,个数超过数组长度一半），那么无论它的各个元素位置是如何分布的，其count经过抵消和增加后，最后一定是大于等于1的。 如果不能保证majority存在，需要检验。 复杂度：O(N)

Attention: 循环时从i = 1开始，从下一个元素开始，因为count已经置1

C++版：

class Solution {

  public:

      int majorityElement(vector<int> &num) {

          int elem = ;

          int count = ;

          for(int i = ; i < num.size(); i++)  {

             if(count == )  {

                 elem = num[i];

                 count = ;

             }

             else    {

                 if(elem == num[i])

                     count++;

                 else

                     count--;

             }

         }

         return elem;

     }

　　};

Python版：

class Solution:

    # @param {integer[]} nums

    # @return {integer}

    def majorityElement(self, nums):

        lenth=len(nums)

        index=0

        count=1

        for i in range(lenth):

            if nums[index]==nums[i]:

                count+=1

            else:

                count-=1

            if count==0:

                index=i

                count+=1

        return nums[index]

巴特西

Majority Element——算法课上的一道题（经典）

最新文章

热门文章