2020-06-11
用最少数量的箭引爆气球
在二维空间中有许多球形的气球。对于每个气球，
提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，
所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。
开始坐标总是小于结束坐标。平面内最多存在10^4个气球。
一支弓箭可以沿着x轴从不同点完全垂直地射出。
在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，
且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。
弓箭一旦被射出之后，可以无限地前进。
我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。。
题解:
思路1：贪心算法
/** * @param {number[][]} points * @return {number} */ var findMinArrowShots = function (points) { if (points.length <= 1) return points.length; // 首先将数组按照第一项的大小排序 第一项相等则按第二项大小排序 points.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]); // count 需要的次数 如果气球大于1 则至少要一次 // tmp 是记录当前射击的右边界值 // 当遍历的每一项的左边界小于此次射击的右边界 则说明此次射击可以射中次气球 let count = 1, tmp = points[0][1]; for (let i = 1; i < points.length; i++) { if (points[i][0] > tmp) { // 如果当前项的左边界大于 tmp 说明此次射击不能够得着这个气球 // 需要增加一次射击 count++; // 增加一次射击后 tmp则为增加的这次射击的右边界了 tmp = points[i][1]; } else tmp = Math.min(tmp, points[i][1]); // 如果此次设计能射中当前气球 // 右边界的大小需要取更小的一项 // 例如 [1, 100] [2, 18] [28, 30] // 当遍历到[2, 18]时， 右边界原先是100 但是 [2,18] 这一项的右边界是 18 必须取更小的18 // 如果不取18 保持100 那么当遍历到[28, 30]时， 也是满足当前项左边界28 小于 当前射击的右边界 100 // 所以必须保证 当前射击的右边界tmp 取值是能射中项的最小的右边界 } return count; };
算法优化 上面是自己想的有点复杂了 有更简单的思路
var findMinArrowShots = function (points) { if (points.length <= 1) return points.length; points.sort((a, b) => a[1] - b[1]); // 按照每一个气球的右边界排序 let count = 1, tmp = points[0][1]; // tmp 记录每一根箭的右边界 // 第一根箭的右边界是points[0][1] 只要后续气球的左边界 <= tmp 则这根箭可以射中它 for (let i = 1; i < points.length; i++) { // 如果当前气球的左边界已经大于箭的右边界 则需要新的一根箭 // 箭的数量+1 tmp更新为新的一根箭的右边界 if (points[i][0] > tmp) { count++; tmp = points[i][1]; } } return count; }