Fork me on GitHub

leetcode之169. 求众数

发表于 | 分类于
字数统计 286 字 | 阅读时长 1 分钟

题目描述：

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

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

示例 1:

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

示例 2:

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

解题思路一：

时间复杂度：$O(n^2)$,空间复杂度:$O(1)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size() / 2 ;
        for(int i = 0; i < nums.size();i++)
        {
            int count = 1;
            for(int j = i + 1; j < nums.size(); j++)
            {
                if(nums[i] == nums[j])
                {                   
                    count++;
                    // cout << count << endl;
                }          
            }
            if(count > n) return nums[i];
        }
        return -1;
    }
};

解题思路二：

时间复杂度：$O(n)$,空间复杂度:$O(n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//map做的
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int, int> m;
        int n = 0;
       
        for(int i = 0; i < nums.size(); i++)
        {
            if(!m.count(nums[i])) m[nums[i]] = 1;
            else m[nums[i]]++;
        }
        
        for(int j = 0; j < nums.size(); j++)
        {
            if(m[nums[j]] > nums.size() / 2)
            {
                n = nums[j];
                break;
            }
        }
        
        return n;
        
    }
};