跳至主要內容
  • Hostloc 空間訪問刷分
  • 售賣場
  • 廣告位
  • 賣站?

4563博客

全新的繁體中文 WordPress 網站
  • 首頁
  • 做完这题我就慌了,怎么会有这样的题目
未分類
19 4 月 2021

做完这题我就慌了,怎么会有这样的题目

做完这题我就慌了,怎么会有这样的题目

資深大佬 : zzzrf 6

原题目的地址在这里,大佬们可以看看有没有更优的解法

做出来觉得和 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);     } } 

大佬有話說 (3)

  • 資深大佬 : Nillouise

    这 oj 没答案给你看吗?这题目应该是排序然后遍历一遍,遍历过程中记录厚度解决,不需要什么 hashMap

  • 主 資深大佬 : zzzrf

    @Nillouise 感谢大佬!我还没资格查看答案…[囧]

  • 資深大佬 : Nillouise

    你可能发错题目了,连接的题目是插入区间,跟你的描述应该没什么关系

文章導覽

上一篇文章
下一篇文章

AD

其他操作

  • 登入
  • 訂閱網站內容的資訊提供
  • 訂閱留言的資訊提供
  • WordPress.org 台灣繁體中文

51la

4563博客

全新的繁體中文 WordPress 網站
返回頂端
本站採用 WordPress 建置 | 佈景主題採用 GretaThemes 所設計的 Memory
4563博客
  • Hostloc 空間訪問刷分
  • 售賣場
  • 廣告位
  • 賣站?
在這裡新增小工具