摧毁小行星

标签: 贪心 数组 排序

难度: Medium

给你一个整数 mass ，它表示一颗行星的初始质量。再给你一个整数数组 asteroids ，其中 asteroids[i] 是第 i 颗小行星的质量。

你可以按 任意顺序 重新安排小行星的顺序，然后让行星跟它们发生碰撞。如果行星碰撞时的质量 大于等于 小行星的质量，那么小行星被 摧毁 ，并且行星会 获得 这颗小行星的质量。否则，行星将被摧毁。

如果所有小行星 都 能被摧毁，请返回 true ，否则返回 false 。

示例 1：

输入：mass = 10, asteroids = [3,9,19,5,21]
输出：true
解释：一种安排小行星的方式为 [9,19,5,3,21] ：
- 行星与质量为 9 的小行星碰撞。新的行星质量为：10 + 9 = 19
- 行星与质量为 19 的小行星碰撞。新的行星质量为：19 + 19 = 38
- 行星与质量为 5 的小行星碰撞。新的行星质量为：38 + 5 = 43
- 行星与质量为 3 的小行星碰撞。新的行星质量为：43 + 3 = 46
- 行星与质量为 21 的小行星碰撞。新的行星质量为：46 + 21 = 67
所有小行星都被摧毁。

示例 2：

输入：mass = 5, asteroids = [4,9,23,4]
输出：false
解释：
行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。
行星把别的小行星摧毁后，质量为 5 + 4 + 9 + 4 = 22 。
它比 23 小，所以无法摧毁最后一颗小行星。

提示：

  • 1 <= mass <= 105
  • 1 <= asteroids.length <= 105
  • 1 <= asteroids[i] <= 105

Submission

运行时间: 103 ms

内存: 29.7 MB

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        while asteroids:
            next_a = []
            for m in asteroids:
                if mass >= m:
                    mass += m
                else:
                    next_a.append(m)
            if len(next_a) == len(asteroids):
                return False
            asteroids = next_a
        return True

Explain

这个题解采取了一个迭代的方法来处理小行星的摧毁问题。初始时，考虑所有的小行星，并试图摧毁它们。对于当前的小行星列表，遍历每颗小行星，如果当前行星的质量大于或等于小行星的质量，则摧毁它并增加行星的质量；如果不是，则将这颗小行星保留到下一个列表中。如果一轮遍历后没有任何小行星被摧毁（即下一个列表的长度与当前列表相同），则返回False。如果所有的小行星都被摧毁了（即下一个列表为空），则返回True。

时间复杂度: O(n^2)

空间复杂度: O(n)

# 定义Solution类
class Solution:
    # 定义主函数，传入行星的初始质量mass和小行星列表
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        # 循环处理所有小行星，直到无更多小行星或无法摧毁更多小行星为止
        while asteroids:
            # 初始化下一轮未被摧毁的小行星列表
            next_a = []
            # 遍历当前小行星列表
            for m in asteroids:
                # 如果行星质量足以摧毁小行星，则增加行星质量
                if mass >= m:
                    mass += m
                # 否则，将此小行星加入下一轮列表
                else:
                    next_a.append(m)
            # 如果本轮没有小行星被摧毁，返回False
            if len(next_a) == len(asteroids):
                return False
            # 更新小行星列表为未被摧毁的小行星
            asteroids = next_a
        # 如果所有小行星都被摧毁，返回True
        return True

Explore

选择迭代逐个检查小行星而不先对它们进行排序，可能是因为排序本身有一个时间复杂度O(n log n)，而迭代检查的过程可能在某些情况下能更早终止执行。例如，如果较早遇到无法摧毁的小行星，就可以立即返回False，而不需要处理整个数组。此外，排序可能不会改变总体的算法复杂度，因为在最坏的情况下，即使排了序，仍然需要遍历整个数组来判断能否摧毁所有小行星。

在题解中，每次迭代开始时都会创建一个空的列表next_a，用来存放那些未被当前行星摧毁的小行星。在迭代过程中，如果发现某个小行星的质量大于当前行星的质量，就将其加入到next_a中。在一轮迭代结束时，如果next_a的长度与原始列表asteroids的长度相同，说明这一轮没有任何一个小行星被摧毁。因此，如果next_a的长度未减少，就会返回False，表示当前行星的质量不足以摧毁任何一个小行星，无法继续进行摧毁操作。

是的，这种处理方式意味着算法对小行星的处理顺序非常敏感。在没有进行排序的情况下，小行星被遍历的顺序将直接影响算法的结果。例如，如果较小的小行星先被处理，可能使行星的质量逐渐增加，从而在后续遍历中摧毁原本不能摧毁的更大的小行星。相反，如果一开始就遇到一个较大的小行星，而行星的质量不足以摧毁它，那么就会直接将其加入到下一轮列表中，可能导致算法提前结束。因此，处理顺序对于这种算法来说是一个关键因素。