原文链接: https://leetcode-cn.com/problems/merge-triplets-to-form-target-triplet

英文原文

A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [ai, bi, ci] describes the ith triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain.

To obtain target, you may apply the following operation on triplets any number of times (possibly zero):

• Choose two indices (0-indexed) i and j (i != j) and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].

  <ul>
      <li>For example, if <code>triplets[i] = [2, 5, 3]</code> and <code>triplets[j] = [1, 7, 5]</code>, <code>triplets[j]</code> will be updated to <code>[max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5]</code>.</li>
  </ul>
  </li>
  

Return true if it is possible to obtain the target triplet [x, y, z] as an element of triplets, or false otherwise.

 

Example 1:

Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and last triplets [[2,5,3],[1,8,4],[1,7,5]]. Update the last triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5]. triplets = [[2,5,3],[1,8,4],[2,7,5]]
The target triplet [2,7,5] is now an element of triplets.

Example 2:

Input: triplets = [[1,3,4],[2,5,8]], target = [2,5,8]
Output: true
Explanation: The target triplet [2,5,8] is already an element of triplets.

Example 3:

Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and third triplets [[2,5,3],[2,3,4],[1,2,5],[5,2,3]]. Update the third triplet to be [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]].
- Choose the third and fourth triplets [[2,5,3],[2,3,4],[2,5,5],[5,2,3]]. Update the fourth triplet to be [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]].
The target triplet [5,5,5] is now an element of triplets.

Example 4:

Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Explanation: It is impossible to have [3,2,5] as an element because there is no 2 in any of the triplets.

 

Constraints:

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

中文题目

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

  <ul>
      <li>例如，<code>triplets[i] = [2, 5, 3]</code> 且 <code>triplets[j] = [1, 7, 5]</code>，<code>triplets[j]</code> 将会更新为 <code>[max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5]</code> 。</li>
  </ul>
  </li>
  

如果通过以上操作我们可以使得目标 三元组 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$

设数组 $\textit{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)
$$

则返回 $\text{true}$，否则返回 $\text{false}$。

代码

[sol1-C++]
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]
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$ 是数组 $\textit{triples}$ 的长度。

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

统计信息

通过次数	提交次数	AC比率
3867	6101	63.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言