Leetcode452. 用最少数量的箭引爆气球

这篇具有很好参考价值的文章主要介绍了Leetcode452. 用最少数量的箭引爆气球。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Every day a Leetcode

题目来源:452. 用最少数量的箭引爆气球

解法1:排序 + 贪心

题解:用最少数量的箭引爆气球

我们首先随机地射出一支箭,再看一看是否能够调整这支箭地射出位置,使得我们可以引爆更多数目的气球。

Leetcode452. 用最少数量的箭引爆气球

如图 1-1 所示,我们随机射出一支箭,引爆了除红色气球以外的所有气球。我们称所有引爆的气球为「原本引爆的气球」,其余的气球为「原本完好的气球」。可以发现,如果我们将这支箭的射出位置稍微往右移动一点,那么我们就有机会引爆红色气球,如图 1-2 所示。

那么我们最远可以将这支箭往右移动多远呢?我们唯一的要求就是:原本引爆的气球只要仍然被引爆就行了。这样一来,我们找出原本引爆的气球中右边界位置最靠左的那一个,将这支箭的射出位置移动到这个右边界位置,这也是最远可以往右移动到的位置:如图 1-3 所示,只要我们再往右移动一点点,这个气球就无法被引爆了。

为什么「原本引爆的气球仍然被引爆」是唯一的要求?别急,往下看就能看到其精妙所在。

因此,我们可以断定:

一定存在一种最优(射出的箭数最小)的方法,使得每一支箭的射出位置都恰好对应着某一个气球的右边界。

这是为什么?我们考虑任意一种最优的方法,对于其中的任意一支箭,我们都通过上面描述的方法,将这支箭的位置移动到它对应的「原本引爆的气球中最靠左的右边界位置」,那么这些原本引爆的气球仍然被引爆。这样一来,所有的气球仍然都会被引爆,并且每一支箭的射出位置都恰好位于某一个气球的右边界了。

有了这样一个有用的断定,我们就可以快速得到一种最优的方法了。考虑所有气球中右边界位置最靠左的那一个,那么一定有一支箭的射出位置就是它的右边界(否则就没有箭可以将其引爆了)。当我们确定了一支箭之后,我们就可以将这支箭引爆的所有气球移除,并从剩下未被引爆的气球中,再选择右边界位置最靠左的那一个,确定下一支箭,直到所有的气球都被引爆。

我们可以写出如下的伪代码:

let points := [[x(0), y(0)], [x(1), y(1)], ... [x(n-1), y(n-1)]],表示 n 个气球
let burst := [false] * n,表示每个气球是否被引爆
let ans := 1,表示射出的箭数

将 points 按照 y 值(右边界)进行升序排序

while burst 中还有 false 值 do
    let i := 最小的满足 burst[i] = false 的索引 i
    for j := i to n-1 do
        if x(j) <= y(i) then
            burst[j] := true
        end if
        ans := ans + 1
    end for
end while

return ans

这样的做法在最坏情况下时间复杂度是 O(n2),即这 n 个气球对应的区间互不重叠,while 循环需要执行 n 次。

代码:

/*
 * @lc app=leetcode.cn id=452 lang=cpp
 *
 * [452] 用最少数量的箭引爆气球
 */

// @lc code=start
class Solution
{
private:
    static bool cmp(const vector<int> A, const vector<int> B)
    {
        return A[1] < B[1];
    }
    bool remainBalloons(vector<bool> &burst)
    {
        for (int i = 0; i < burst.size(); i++)
            if (burst[i] == false)
                return true;
        return false;
    }

public:
    int findMinArrowShots(vector<vector<int>> &points)
    {
        if (points.empty())
            return 0;
        int n = points.size();
        vector<bool> burst(n, false);
        int ans = 0;
        sort(points.begin(), points.end(), cmp);
        while (remainBalloons(burst))
        {
            int i = 0;
            while (i < n && burst[i] == true)
                i++;
            for (int j = i; j < n; j++)
            {
                if (points[j][0] <= points[i][1])
                    burst[j] = true;
            }
            ans++;
        }
        return ans;
    }
};
// @lc code=end

结果:超时

Leetcode452. 用最少数量的箭引爆气球

复杂度分析:

时间复杂度:O(n2),其中 n 是数组 points 的长度。排序的时间复杂度为 O(nlogn),对所有气球进行遍历并计算答案的时间复杂度为 O(n),其在渐进意义下小于前者,因此可以忽略。

空间复杂度:O(n),其中 n 是数组 points 的长度。我们用到了长度为 n 的复制数组 burst。

解法2:

那么我们如何继续进行优化呢?

事实上,在内层的 j 循环中,当我们遇到第一个不满足 x(j)≤y(i) 的 j 值,就可以直接跳出循环,并且这个 y(j) 就是下一支箭的射出位置。为什么这样做是对的呢?我们考虑某一支箭的索引 it 以及它的下一支箭的索引 jt,对于索引在 jt 之后的任意一个可以被 it 引爆的气球,记索引为 j0 ,有:x(j0)≤y(it)。

由于 y(it)≤y(jt) 显然成立,那么 x(j0)≤y(jt) 也成立,也就是说:当前这支箭在索引 jt(第一个无法引爆的气球)之后所有可以引爆的气球,下一支箭也都可以引爆。因此我们就证明了其正确性,也就可以写出如下的伪代码:

let points := [[x(0), y(0)], [x(1), y(1)], ... [x(n-1), y(n-1)]],表示 n 个气球
let pos := y(0),表示当前箭的射出位置
let ans := 1,表示射出的箭数

将 points 按照 y 值(右边界)进行升序排序

for i := 1 to n-1 do
    if x(i) > pos then
        ans := ans + 1
        pos := y(i)
    end if
end for

return ans

这样就可以将计算答案的时间从 O(n2) 降低至 O(n)。

代码:

class Solution
{
private:
    static bool cmp(const vector<int> &A, const vector<int> &B)
    {
        return A[1] < B[1];
    }

public:
    int findMinArrowShots(vector<vector<int>> &points)
    {
        if (points.empty())
            return 0;
        // sort(points.begin(), points.end(), [](const vector<int> &u, const vector<int> &v)
        //      { return u[1] < v[1]; });
        sort(points.begin(), points.end(), cmp);
        int pos = points[0][1];
        int ans = 1;
        for (const vector<int> &balloon : points)
        {
            if (balloon[0] > pos)
            {
                pos = balloon[1];
                ans++;
            }
        }
        return ans;
    }
};

结果:

Leetcode452. 用最少数量的箭引爆气球

复杂度分析:

时间复杂度:O(nlogn),其中 n 是数组 points 的长度。排序的时间复杂度为 O(nlogn),对所有气球进行遍历并计算答案的时间复杂度为 O(n),其在渐进意义下小于前者,因此可以忽略。

空间复杂度:O(logn),其中 n 是数组 points 的长度。即为排序需要使用的栈空间。文章来源地址https://www.toymoban.com/news/detail-461997.html

到了这里,关于Leetcode452. 用最少数量的箭引爆气球的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode刷题笔记【26】:贪心算法专题-4(柠檬水找零、根据身高重建队列、用最少数量的箭引爆气球)

    参考前文 参考文章: LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和) LeetCode刷题笔记【24】:贪心算法专题-2(买卖股票的最佳时机II、跳跃游戏、跳跃游戏II) LeetCode刷题笔记【25】:贪心算法专题-3(K次取反后最大化的数组和、加油站、分发糖

    2024年02月09日
    浏览(47)
  • 用最少数量的箭引爆气球【贪心算法】

    用最少数量的箭引爆气球 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处

    2024年02月10日
    浏览(36)
  • day31贪心算法 用最少数量的箭引爆气球 和无重叠区间

    题目描述 题目分析: x轴向上射箭,12一支,重叠的需要一支,3-8一支,7-16一支 返回2; 就是让重叠的气球尽量在一起,局部最优;用一支弓箭,全局最优就是最少弓箭; 如何去寻找重叠的气球?和记录弓箭数? 1.对所有气球排序;(左边界排序如上图); 2. if 如果第i个气

    2024年02月16日
    浏览(48)
  • 每日一题——LeetCode1189.气球的最大数量

    方法一 个人方法: 统计text字符串中\\\'b\\\'、\\\'a\\\'、\\\'l\\\'、\\\'o\\\'、\\\'n\\\' 这几个字符出现的次数 l和n需要两个才能拼成一个balloon,所以碰到l和o加1,其他字符加2 最后求出出现次数最少的那个字符再除以2就是能拼凑成的单词数量,避免出现小数要使用向下取整 消耗时间和内存情况: 方法

    2024年02月01日
    浏览(36)
  • 引脚数量最少的单片机

    2款SOT23-6封装单片机介绍 PMS150C-U06 整盘单价:¥0.19688,该芯片为中国台湾品牌PADAUK(应广) SQ013L-SOT23-6-TR 整盘单价:¥0.27876,该芯片为国产:holychip(芯圣电子) 上述价格为2024-3-29参考价格,有量的情况下,都可以和厂家谈 有时候我们遇到SOT23-6的,可能不知道是什么器件,如2脚

    2024年04月13日
    浏览(43)
  • 华为OD机试 - 最少数量线段覆盖| 机试题算法思路 【2023】

    华为OD机试 - 简易压缩算法(Python) | 机试题算法思路 【2023】 华为OD机试题 - 获取最大软件版本号(JavaScript) 华为OD机试 - 猜字谜(Python) | 机试题+算法思路 【2023】 华为OD机试 - 删除指定目录(Python) | 机试题算法思路 【2023】 华为OD机试 - 自动曝光(Python) | 机试题算法

    2023年04月25日
    浏览(44)
  • 【动态规划】LeetCode 312. 戳气球 --区间DP问题

      Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接       我会一直往里填充内容哒! 🌈LeetCode专栏:专栏链接       目前在刷初级算法的LeetBook 。若每日一题当中有力所能

    2023年04月16日
    浏览(39)
  • LeetCode452. Minimum Number of Arrows to Burst Balloons

    There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons. Arrows can be shot up directly vertically (in

    2024年02月04日
    浏览(44)
  • 华为OD机试 - 最少数量线段覆盖 - 二叉树(Java 2023 B卷 100分 考试抽中题)

    华为OD机试 2023B卷题库疯狂收录中,刷题 点这里

    2024年02月11日
    浏览(49)
  • LeetCode //C - 452. Minimum Number of Arrows to Burst Balloons

    There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [ x s t a r t , x e n d x_{start}, x_{end} x s t a r t ​ , x e n d ​ ] denotes a balloon whose horizontal diameter stretches between x s t a r t x_{start} x s t a r t ​ and x e n d x_{end} x

    2024年02月12日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包