LeetCode—— 多数元素

题目描述

给定一个大小为 n 的数组，找到其中的多数元素。
多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

一、CPP

1. 摩尔投票法：

解题思路:如果我们把众数记为 +1，把其他数记为 −1 ，将它们全部加起来，显然和大于 0 ，从结果本身我们可以看出众数比其他数多。实现方法就是，默认一个数为众数，如果下一个数的值还为此数，则计数器加1，否则计数器减1。如果计数器减为0，则把下一个遇到的数记为众数再进行上述操作。由于众数的个数大于n/2。所以遍历完数组之后，众数的计数器大于0，majorityNum记录的值即为众数。
时间复杂度:O(n)。
空间复杂度:O(1)。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        
        //初始化
        int count = 1;
        int majorityNum = nums.at(0);

        for(int i = 1;i<nums.size();i++){
            
            if(count == 0){
                majorityNum = nums.at(i);
                count = 1;
            }
            else{

                if(nums.at(i)==majorityNum){
                    count++;
                }
                else{
                    count--;
                }

            }

        }

        return majorityNum;
        
    }
};

解法参考：https://leetcode-cn.com/problems/majority-element/solution/du-le-le-bu-ru-zhong-le-le-ru-he-zhuang-bi-de-qiu-/

2. 排序法：

解题思路:使用sort把vector内的元素进行排序，如果一个数出现次数大于n/2，那么nums[n/2]则为此数。
时间复杂度:O(nlogn)。sort排序的时间复杂度为O(nlogn)。
空间复杂度:O(1)。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        
        int length = nums.size();

        sort(nums.begin(),nums.end());

        return nums[length/2];
        
    }
};

3. hashtable法：

解题思路:把数组元素作为key，出现频次作为value。如果频次大于majority (length / 2 + 1)。则返回。
时间复杂度:O(n)。
空间复杂度:O(n)。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        
        unordered_map<int,int> hashtable;
        int majority = nums.size() / 2 + 1;

        for(int i = 0;i < nums.size(); i++){
            if(hashtable.count(nums[i]) > 0){
                hashtable[nums[i]]++;
            }
            else{
                hashtable[nums[i]] = 1;
            }
            
            if(hashtable[nums[i]] >= majority){
                return nums[i];
            }
        }
         return 0;
    }
};

4. 暴力法：

解题思路:两层遍历。第一层遍历得到数i，第二层遍历统计数i的次数，如果出现次数大于majority (length / 2 + 1)。则返回。
时间复杂度:O(n²)。
空间复杂度:O(1)。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int length = nums.size();
        int majority = length / 2 + 1;

        for(int i = 0;i<length;i++){

            int count = 0;
            for(int j = 0;j<length;j++){
                if(nums[i] == nums[j]){
                    count++;
                }
            }

            if(count>=majority){
                return nums[i];
            }

        }
        return 0;
    }
};

二、Java（摩尔投票法）

class Solution {
    public int majorityElement(int[] nums) {

        //初始化
        int majorityNum = nums[0];
        int count = 1;
      
        for(int i = 1;i<nums.length;i++){

            if(count == 0){
                majorityNum = nums[i];
                count = 1;
            }
            else{

                if(nums[i] == majorityNum){
                    count++;
                }
                else{
                    count--;
                }
            }
        }
        return majorityNum;
    }
}

三、Python（摩尔投票法）

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 初始化
        count = 1
        majorityNum = nums[0]

        # 注意i的下标范围
        for i in range(1,len(nums)):
            if count == 0:
                majorityNum = nums[i];
                count = 1
            else:
                if nums[i] == majorityNum:
                    count += 1;
                else:
                    count -= 1;
        return majorityNum;

四、各语言及算法时间复杂度

各语言及算法时间复杂度