合并若干三元组以形成目标三元组

标签: 贪心 数组

难度: Medium

三元组 是一个由三个整数组成的数组。给你一个二维整数数组 triplets ，其中 triplets[i] = [ai, bi, ci] 表示第 i 个 三元组 。同时，给你一个整数数组 target = [x, y, z] ，表示你想要得到的 三元组 。

为了得到 target ，你需要对 triplets 执行下面的操作 任意次（可能 零 次）：

  • 选出两个下标（下标 从 0 开始 计数）i 和 j（i != j），并 更新 triplets[j] 为 [max(ai, aj), max(bi, bj), max(ci, cj)] 。
    • 例如，triplets[i] = [2, 5, 3] 且 triplets[j] = [1, 7, 5]，triplets[j] 将会更新为 [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5] 。

如果通过以上操作我们可以使得目标 三元组 target 成为 triplets 的一个 元素 ，则返回 true ；否则，返回 false 。

 

示例 1：

输入：triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
输出：true
解释：执行下述操作：
- 选择第一个和最后一个三元组 [[2,5,3],[1,8,4],[1,7,5]] 。更新最后一个三元组为 [max(2,1), max(5,7), max(3,5)] = [2,7,5] 。triplets = [[2,5,3],[1,8,4],[2,7,5]]
目标三元组 [2,7,5] 现在是 triplets 的一个元素。

示例 2：

输入：triplets = [[1,3,4],[2,5,8]], target = [2,5,8]
输出：true
解释：目标三元组 [2,5,8] 已经是 triplets 的一个元素。

示例 3：

输入：triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
输出：true
解释：执行下述操作：
- 选择第一个和第三个三元组 [[2,5,3],[2,3,4],[1,2,5],[5,2,3]] 。更新第三个三元组为 [max(2,1), max(5,2), max(3,5)] = [2,5,5] 。triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。
- 选择第三个和第四个三元组 [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。更新第四个三元组为 [max(2,5), max(5,2), max(5,3)] = [5,5,5] 。triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]] 。
目标三元组 [5,5,5] 现在是 triplets 的一个元素。

示例 4：

输入：triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
输出：false
解释：无法得到 [3,2,5] ，因为 triplets 不含 2 。

 

提示：

  • 1 <= triplets.length <= 105
  • triplets[i].length == target.length == 3
  • 1 <= ai, bi, ci, x, y, z <= 1000

Submission

运行时间: 100 ms

内存: 52.9 MB

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        arr = [[] for _ in range(3)]
        for x, y, z in triplets:
            if x <= target[0] and y <= target[1] and z <= target[2]:
                arr[0].append(x)
                arr[1].append(y)
                arr[2].append(z)
        if not arr[0]:
            return False
        return max(arr[0]) == target[0] and max(arr[1]) == target[1] and max(arr[2]) == target[2]

Explain

这个题解采用了过滤和验证的方法来解决问题。首先，遍历所有的三元组，将那些每个元素都不超过目标三元组对应元素的三元组筛选出来。筛选出的三元组分别保存到三个列表中，每个列表只保存对应位置的值。然后，检查这三个列表中的最大值是否分别与目标三元组的三个值相匹配。如果都匹配，则返回true；否则返回false。这种方法有效地避免了不必要的三元组合并，通过直接比较筛选后的最大值与目标值是否相等来判断是否能够得到目标三元组。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        arr = [[] for _ in range(3)]  # 为每个坐标轴创建一个列表以存储合格的三元组的值
        for x, y, z in triplets:  # 遍历每个三元组
            if x <= target[0] and y <= target[1] and z <= target[2]:  # 检查三元组是否每一位都不超过目标
                arr[0].append(x)  # 存储x值
                arr[1].append(y)  # 存储y值
                arr[2].append(z)  # 存储z值
        if not arr[0]:  # 如果没有任何合格的三元组，则直接返回false
            return False
        return max(arr[0]) == target[0] and max(arr[1]) == target[1] and max(arr[2]) == target[2]  # 检查每个坐标轴的最大值是否等于目标值

Explore

筛选出每个元素都不超过目标三元组对应元素的三元组是为了减少计算量和提高效率。如果尝试所有可能的三元组组合，组合数量将会非常庞大，特别是当三元组列表较大时，这将导致时间复杂度过高，可能达到指数级。通过筛选，我们可以直接排除那些无论如何也不能满足条件的三元组，从而仅仅关注那些有潜力达到目标三元组的值的三元组，这样可以大大简化问题的复杂度。

是的，这种情况是可能的。即使筛选出的三元组每个元素都不超过目标三元组对应的元素，也可能没有任何一个三元组的元素能够完全达到目标三元组的每一个值。例如，如果目标三元组是 [5, 5, 5]，但所有筛选出的三元组的最大值分别是 [4, 4, 4]，则无法通过这些三元组达到目标。因此，我们需要在最后验证筛选后的每个坐标轴的最大值是否等于目标值。

在代码实现中，如果某个坐标轴的数组为空（即没有任何三元组的该维度值小于或等于目标三元组的对应值），则直接返回false。这是因为如果任何一个维度没有合格的三元组值，则无法通过任何组合达到目标三元组的该维度值。处理空数组的情况是必要的，因为计算空数组的最大值会引发错误或异常。

筛选后的三元组列表中的最大值并不一定能达到目标三元组的对应值。这种方法的局限性在于，它依赖于输入三元组的分布。如果没有足够的三元组覆盖目标值的每一个维度，即使单个维度的最大值达到了目标，其他维度可能仍达不到，从而无法完全构成目标三元组。因此，这种方法适用于那些三元组比较均匀分布且能够涵盖各个维度的情况。