文档章节

[leetcode 周赛 149] 1157 子数组中占绝大多数的元素

o
 osc_wws45aot
发布于 2019/08/20 10:42
字数 1471
阅读 5
收藏 0

精选30+云产品,助力企业轻松上云!>>>

1157 Online Majority Element In Subarray 子数组中占绝大多数的元素

描述

实现一个 MajorityChecker 的类,它应该具有下述几个 API

  • MajorityChecker(int[] arr) 会用给定的数组 arr 来构造一个 MajorityChecker 的实例。

  • int query(int left, int right, int threshold) 有这么几个参数:

    • 0 <= left <= right < arr.length 表示数组 arr 的子数组的长度。
    • 2 * threshold > right - left + 1,也就是说阈值 threshold 始终比子序列长度的一半还要大。 每次查询 query(...) 会返回在 arr[left], arr[left+1], ..., arr[right] 中至少出现阈值次数 threshold 的元素,如果不存在这样的元素,就返回 -1
  • 示例:

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // 返回 1
majorityChecker.query(0,3,3); // 返回 -1
majorityChecker.query(2,3,2); // 返回 2

  • 提示:

1 <= arr.length <= 20000 1 <= arr[i] <= 20000 对于每次查询,0 <= left <= right < len(arr) 对于每次查询,2 * threshold > right - left + 1 查询次数最多为 10000

思路

  • 首先读题:

    • 查询query需要拥有一个出现次数超过查询长度一半的元素 众数(出现次数超过总数一半的元素)思想: 拥有众数的数组, 数组内元素两两对消(元素不相等)或两两相融(元素相等), 剩下的必定是众数
    • 查询次数上限10000, 需要保证查询速率
    • 阈值次数threshold, 在查询范围内, 众数出现次数获取 可以使用二分查找左右边界
  • 可以使用动态规划的思想:

    • 状态转移公式

l查询左边界 r查询右边界 val查询区域众数 cnt众数在查询区域出现次数
- 子问题合并

两子问题返回众数相等, 则出现次数相加, 不等则出现次数大减小

以此思想可以建立线段树存储数据来加速查询速率

代码实现

使用线段树提前计算区域众数来加速查询

// 通过线段树来存储某些区域的众数和计数 以此来加速查询
class MajorityChecker {
    // idx 存储数组出现元素种类 以及该元素下标索引
    // [1, 2, 2, 1, 1, 2] --> [[1 : 0, 3, 4], [2 : 1, 2, 5]]
    HashMap<Integer, ArrayList<Integer>> idx;
    // 线段树的根节点
    SegTreeNode root;
    // key 所查找的区域众数
    // count 所查找的区域众数出现次数
    // 注意: 数组元素范围不包括0
    int key=0, count=0;

    /** 
     * 初始化 
     * 元素索引表idx 和 线段树root
     * 
     * @param arr 被查询数组
     * */
    public MajorityChecker(int[] arr) {
        idx = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (!idx.containsKey(arr[i])) 
                idx.put(arr[i], new ArrayList<Integer>());
            idx.get(arr[i]).add(i);
        }
        
        root = buildTree(arr, 0, arr.length-1);
    }
    
    /**
     * 查询区域众数 是否超过阈值
     * 
     * @param left 查询区域左边界
     * @param right 查询区域右边界
     * @param threshold 用来判断众数的出现次数阈值  
     * @return key/-1 如果所查询众数key的查询区域出现次数超过阈值threshold则返回key, 否则返回-1
     * */
    public int query(int left, int right, int threshold) {
        // 初始化 所查询众数key 及辅助判断的计数count
        key = 0; count = 0;
        // 查询线段树
        searchSegTree(root, left, right);
        // 如果查询区域没有众数 即key没被更改
        // 或者
        // 所查询出来的众数 在原数组中根本没有超出阈值的能力
        if (key == 0 || idx.get(key).size() < threshold) return -1;
        
        // 上确界 排序数组中 第一个大于right的下标
        int r = upper_bound(idx.get(key), right);
        // 下确界 排序数组中 第一个大于等于left的下标
        int l = lower_bound(idx.get(key), left);
        count = r - l;
        
        return count >= threshold ? key : -1;
    }
    
    // 排序数组中 第一个大于tar的下标
    int upper_bound(List<Integer> list, int tar) {
        int l = 0, r = list.size();
        while (l < r) {
            int mid = l + (r-l)/2;
            if (list.get(mid) <= tar) l = mid+1;
            else r = mid;
        }
        
        return l;
    }

    // 排序数组中 第一个大于等于tar的下标
    int lower_bound(List<Integer> list, int tar) {
        int l = 0, r = list.size()-1;
        while (l < r) {
            int mid = l + (r-l)/2;
            if (list.get(mid) < tar) l = mid+1;
            else r = mid;
        }
        
        return l;
    }
    
    /**
     * 构建线段树
     * 
     * @param arr 被构建数组
     * @param l 构建节点的左值 表示查询区域左边界
     * @param r 构建节点的右值 表示查询区域右边界
     * @return 以构建完成的线段树节点
     * */
    private SegTreeNode buildTree(int[] arr, int l, int r) {
        if (l > r) return null;
        
        // 初始一个线段树节点
        SegTreeNode root = new SegTreeNode(l, r);
        // 叶子节点
        if (l == r) {
            // 众数就是当前值 计数为1
            root.val = arr[l]; root.count = 1;
            return root;
        }
        
        int mid = (l+r)/2;
        // 构建左子节点
        root.left = buildTree(arr, l, mid);
        // 构建右子节点
        root.right = buildTree(arr, mid+1, r);
        // 整合父节点
        makeRoot(root);
        
        return root;
    }
    
    /**
     * 整合一个父节点
     * 
     * @param root 被整合节点
     * */
    private void makeRoot(SegTreeNode root) {
        if (null == root) return;
        
        // 如果该节点有左子节点 该节点的值"先"等于左子节点
        if (root.left != null) {
            root.val = root.left.val;
            root.count = root.left.count;
        }
        // 如果该节点还有右子节点 融合父节点和子节点
        if (root.right != null) {
            if (root.val == root.right.val) 
                root.count = root.count + root.right.count;
            else {
                if (root.count >= root.right.count) 
                    root.count = root.count - root.right.count;
                else {
                    root.val = root.right.val; 
                    root.count = root.right.count - root.count;
                }
            }
        }
    }
    
    /**
     * 查询线段树
     * 
     * @param root 被查询节点
     * @param l 需要查询的范围左边界
     * @param r 需要查询的范围右边界
     * */
    private void searchSegTree(SegTreeNode root, int l, int r) {
        if (null==root | l > r) return;
        if (root.l > r | root.r < l) return;
        
        // 当查询边界覆盖节点边界 该节点就是查询区域
        if (l <= root.l && root.r <= r) {
            if (key == root.val) count += root.count;
            else if (count <= root.count) {
                key = root.val;
                count = root.count - count;
            } else {
                count = count - root.count;
            }
            return;
        }
        
        int mid = (root.r + root.l)/2;
        // root.l <= l <= mid 左节点也可以是查询区域
        if (l <= mid) {
            searchSegTree(root.left, l, r);
        }
        // mid+1 <= r <= root.r 右节点也可以是查询区域
        if (r >= mid+1) {
            searchSegTree(root.right, l, r);
        }
    }
    
    /**
     * 线段树节点 类
     * 用于存储区域边界/众数和计数 并且连接下一节点
     * */
    static class SegTreeNode {
        // l 所存储区域左边界
        // r 所存储区域右边界
        // val 所存储区域众数
        // count 所存储区域众数计数(出现次数)
        int l, r, val, count;
        SegTreeNode left, right;
        
        SegTreeNode(int l, int r) {
            this.l = l; this.r = r;
            val = 0; count = 0;
            left = null; right = null;
        }
    }
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
【LeetCode】周赛汇总

周赛 No.196(待编辑) | # | 算法 | 状态| 补题时间||:--|:--|:--| :-- || A. 数组中两元素的最大乘积| 最大与次大 | ac | ...| B. 切割后面积最大的蛋糕 | 思维题,排序 | 理解 | ...| C. ...

秋夕点灯笼
05/24
1
0
LeetCode刷题总结-数组篇(上)

数组是算法中最常用的一种数据结构,也是面试中最常考的考点。在LeetCode题库中,标记为数组类型的习题到目前为止,已累计到了202题。然而,这202道习题并不是每道题只标记为数组一个考点,大...

osc_p3rdih8s
2019/11/03
2
0
[leetcode 双周赛 6] 1150 检查一个数是否在数组中占绝大多数

1150 Check If a Number Is Majority Element in a Sorted Array 检查一个数是否在数组中占绝大多数 描述 给出一个按 非递减 顺序排列的数组 ,和一个目标数值 。 假如数组 nums 中绝大多数元...

osc_c847shr3
2019/08/13
3
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringCloud- 第六篇 Hystrix参数配置(三)

1:概述 Hystrix使用Archaius作为配置属性的默认实现。官方配置文档: https://github.com/Netflix/Hystrix/wiki/Configuration 每个属性有四个优先级,依次增大: 1:代码的全局默认值 2:动...

osc_7z601p6x
11分钟前
0
0
SpringBoot2 整合JTA组件,多数据源事务管理

本文源码:GitHub·点这里 || GitEE·点这里 一、JTA组件简介 1、JTA基本概念 JTA即Java-Transaction-API,JTA允许应用程序执行分布式事务处理,即在两个或多个网络计算机资源上访问并且更新...

osc_sju4uxml
12分钟前
0
0
Springboot + Vue + shiro 实现前后端分离、权限控制

本文总结自实习中对项目的重构。原先项目采用Springboot+freemarker模版,开发过程中觉得前端逻辑写的实在恶心,后端Controller层还必须返回Freemarker模版的ModelAndView,逐渐有了前后端分...

osc_lbt7zo1x
14分钟前
0
0
docker-compose部署配置jenkins

docker-compose部署配置jenkins 一、docker-compose文件 version: '3.1'services: jenkins: image: jenkins/jenkins:lts volumes: - /data/jenkins/:/var/jenkins_home ......

osc_4p2c0ecc
16分钟前
3
0
第五周

1、查找/etc目录下大于1M且类型为普通文件的所有文件 2、打包/etc/目录下面所有conf结尾的文件,压缩包名称为当天的时间,并拷贝到/usr/local/src目录备份。 3、利用sed 取出ifconfig命令中本...

osc_hxm151is
17分钟前
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部