229. 多数元素 II

一、题目

1、题目描述

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：
输入：nums = [3,2,3]
输出：[3]

示例 2：
输入：nums = [1]
输出：[1]

示例 3：
输入：nums = [1,2]
输出：[1,2]

提示：
1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。

2、基础框架

• C++版本给出的基础框架如下：

3、原题链接

二、解题报告

1、思路分析

  $(1)$排序，遍历的同时计数

2、时间复杂度

3、代码详解

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int>ret;
        sort(nums.begin(), nums.end());
        int t = nums.size() / 3;
        int cnt = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[i-1]) {
                if (cnt > t) {
                    ret.push_back(nums[i-1]);
                }
                cnt = 1;
            } else {
                cnt++;
            }
        }
        if (cnt > t) {
            ret.push_back(nums[nums.size()-1]);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三、本题小知识