[leetcode/lintcode 题解] 算法面试高频题详解: 主元素 III

简介: [leetcode/lintcode 题解] 算法面试高频题详解: 主元素 III

描述
给定一个整型数组,找到主元素,它在数组中的出现次数严格大于数组元素个数的1/k。

数组中只有唯一的主元素

在线评测地址:领扣题库官网

样例1
输入: [3,1,2,3,2,3,3,4,4,4] and k=3, 
输出: 3.
AI 代码解读
样例2
输入: [1,1,2] and k=3, 
输出: 1.
AI 代码解读

挑战
要求时间复杂度为O(n),空间复杂度为O(k)

算法:hashmap
当一个数的出现次数大于等于元素总数除以k向上取整时说明找到答案
将所有数字都用map存下来,并存下出现次数
遍历这个map,找到次数大于总数k分之一的元素
复杂度分析

  • 时间复杂度O(n)

    • n为数组大小
  • 空间复杂度O(n)

    • n为数组大小

代码

  public class Solution {
    /*
     * @param nums: a list of integers
     * @return: The majority number that occurs more than 1/3
     */
    public int majorityNumber(List<Integer> nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int n = nums.size();
        if(n == 0){
            return -1;
        }
        int count = n/k + 1;
        //遍历nums
        Iterator it = nums.iterator();
        while(it.hasNext()){
            Integer tmp = (Integer)it.next();
            if(map.containsKey(tmp)){
                int m = (int)map.get(tmp) + 1;
                map.put(tmp, m);
                // 判断是否大于等于k分之一
                if(m >= count){
                    return tmp;
                }
            }
            else{
                map.put(tmp, 1);
            }
        }
        return nums.get(0);
    }
}
AI 代码解读

更多题解参考:九章官网solution

目录
打赏
0
0
0
0
6
分享
相关文章
|
4月前
|
面试场景题:如何设计一个抢红包随机算法
本文详细解析了抢红包随机算法的设计与实现,涵盖三种解法:随机分配法、二倍均值法和线段切割法。随机分配法通过逐次随机分配金额确保总额不变,但易导致两极分化;二倍均值法优化了金额分布,使每次抢到的金额更均衡;线段切割法则将总金额视为线段,通过随机切割点生成子金额,手气最佳金额可能更高。代码示例清晰,结果对比直观,为面试中类似算法题提供了全面思路。
978 16
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
197 16
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
101 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
469 2
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
142 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
11月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
115 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
234 2

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等