题目地址(229. 多数元素 II)

题目地址(229. 多数元素 II)

https://leetcode.cn/problems/majority-element-ii/

题目描述

给定一个大小为 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)的算法解决此问题。

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        if(nums.length == 1) return Arrays.asList(nums[0]);
        //[ n / 3 ] 只有两个
        int count1 = 1, count2 = 0;
        int num1 = nums[0], num2 = nums[0]; //最多的两位数
        for(int i = 1; i< nums.length;i++){ 
            if(num1 == nums[i]){
                 count1++; 
                 continue;
            }else if(num2 == nums[i]){
                 count2++;
                 continue;                 
            }
            if(count1 == 0){
                num1 = nums[i]; 
                count1 = 1;
                continue; 
            }
            if(count2 == 0){
                num2 = nums[i];
                count2 = 1;
                continue;
            }
            count1--;
            count2--;
        }
        count1 = count2 = 0;
        for(int num : nums){
            if( num == num1 ){
                 count1 ++;
            }else if( num == num2 ){
                 count2++;
            }
        }
        List<Integer> res = new ArrayList<>();
        if( count1 > nums.length / 3 ) res.add(num1);
        if( count2 > nums.length / 3 ) res.add(num2);
        return res;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$