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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

三元组 是一个由三个整数组成的数组。给你一个二维整数数组 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

方法一：合并尽可能多的三元组

提示 1

设数组 triplets 的长度为 n。

题目等价于让我们选择若干个下标 i_1, i_2, \cdots, i_k，且 i_1 < i_2 < \cdots < i_k \leq n，使得：

\begin{cases}
x = \max { a_{i_1}, a_{i_2}, \cdots, a_{i_k} } \
y = \max { b_{i_1}, b_{i_2}, \cdots, b_{i_k} } \
z = \max { c_{i_1}, c_{i_2}, \cdots, c_{i_k} }
\end{cases}

这里的正确性在于，我们每次执行的操作是选择两个三元组每一个位置中的较大值，因此：

  • 同一个下标对应的三元组选择多次是没有意义的，每个三元组会被选择 0 或 1 次；

  • 选择三元组的顺序也是可以任意交换的。

提示 2

对于任意一个三元组 (a_i, b_i, c_i)：

  • 如果 a_i > x 或者 b_i > y 或者 c_i > z，那么选择该三元组是不合理的；

  • 否则，一定有 a_i \leq x 并且 b_i \leq y 并且 c_i \leq z。由于所有的操作都是 \max 操作，因此选择这个三元组并没有什么坏处，它不会让我们原本得到 (a_i, b_i, c_i) 的某种可行选择变得不可行，因为：

    \big( \max{x, a_i}, \max{y, b_i}, \max{z, c_i} \big) = (x, y, z)

    是显然成立的。

思路与算法

根据提示 2，我们只需要遍历所有的三元组，如果 a_i \leq x 并且 b_i \leq y 并且 c_i \leq z，那么我们就选择该三元组。

设 a, b, c 分别是我们选择的所有三元组 a_i, b_i, c_i 中的最大值。在遍历结束后，如果有：

(a, b, c) = (x, y, z)

则返回 true，否则返回 false。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        int x = target[0], y = target[1], z = target[2];
        int a = 0, b = 0, c = 0;

        for (const auto& triplet: triplets) {
            int ai = triplet[0], bi = triplet[1], ci = triplet[2];
            if (ai <= x && bi <= y && ci <= z) {
                tie(a, b, c) = tuple{max(a, ai), max(b, bi), max(c, ci)};
            }
        }

        return tie(a, b, c) == tie(x, y, z);
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        x, y, z = target
        a, b, c = 0, 0, 0
        
        for ai, bi, ci in triplets:
            if ai <= x and bi <= y and ci <= z:
                a, b, c = max(a, ai), max(b, bi), max(c, ci)
        
        return (a, b, c) == (x, y, z)

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 triples 的长度。

  • 空间复杂度：O(1)。

 Comments
On this page
1899-合并若干三元组以形成目标三元组