Android防重复点击 存量客户 css facebook wcf service directory scrapy jestjs vb6 seo外包优化 svn默认安装路径 vm虚拟化引擎 python练习题 数据库查询 python3文件操作 python语言编程 javaswitch语句 java时间格式化 java成员变量 java获得当前日期 linux远程 网络适配器驱动 python入门经典 js删除数组指定元素 碧桂园园宝 微信临时链接多久失效 vue定时器 linux格式化硬盘 黑道圣徒4去马赛克补丁 掘地鼠炖肉 西门子触摸屏编程软件 linux添加用户 易语言皮肤模块 x截屏 超级好友 云挂机软件 mdb是什么文件 kms audition消除人声
当前位置: 首页 > 学习教程  > 编程语言

【LeetCode】229. Majority Element II 求众数 II(Medium)(JAVA)

2020/12/5 9:44:41 文章标签:

【LeetCode】229. Majority Element II 求众数 II(Medium)(JAVA) 题目地址: https://leetcode.com/problems/majority-element-ii/ 题目描述: Given an integer array of size n, find all elements that appear mo…

【LeetCode】229. Majority Element II 求众数 II(Medium)(JAVA)

题目地址: https://leetcode.com/problems/majority-element-ii/

题目描述:

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Follow-up: Could you solve the problem in linear time and in O(1) space?

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

Constraints:

  • 1 <= nums.length <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

题目大意

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

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

解题方法

  1. 暴力的解法就是用一个 Map 把出现的 num 和对应的次数存起来,遇到超过 n / 3 次的元素就存进结果,时间复杂度为 O(n),但是空间复杂度为 O(n),不符合空间复杂度为 O(1) 的要求
  2. 因为超过 n / 3 次的元素最多两个,所以用两个元素来表示可能超过 n / 3 出现次数的元素,后续如果是这两个元素就次数 +1, 如果不是就都 -1
  3. 最后再通过一次遍历,判断最后这两个中的元素是否是超过了 n / 3,因为可能不存在超过 n / 3 的元素
  4. note: 为什么可能是元素都需要 -1 呢?这样不是减了两次了吗?因为所有元素不相等的时候,表示所有的 count 都是大于等于 1,如果有一个元素等于 0 这次就不会有 - 1 操作了,后续要减的时候都要补上
class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        if (nums.length == 0) return list;
        if (nums.length == 1) {
            list.add(nums[0]);
            return list;
        }
        int[] count = new int[2];
        int[] arr = new int[2];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            boolean flag = false;
            for (int j = 0; j < arr.length && !flag; j++) {
                if (arr[j] == nums[i]) {
                    flag = true;
                    count[j]++;
                }
            }
            for (int j = 0; j < arr.length && !flag; j++) {
                if (count[j] == 0) {
                    flag = true;
                    count[j]++;
                    arr[j] = nums[i];
                }
            }
            if (!flag) {
                for (int j = 0; j < count.length; j++) {
                    count[j]--;
                }
            }
        }
        for (int i = 0; i < count.length; i++) {
            count[i] = 0;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[j] == nums[i]) {
                    count[j]++;
                    break;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (count[i] > nums.length / 3) list.add(arr[i]);
        }
        return list;
    }
}

执行耗时:2 ms,击败了96.27% 的Java用户
内存消耗:42.5 MB,击败了54.62% 的Java用户

欢迎关注我的公众号,LeetCode 每日一题更新

本文链接: http://www.dtmao.cc/news_show_450067.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?