跳转至

3572. 选择不同 X 值三元组使 Y 值之和最大

题目描述

给你两个整数数组 x 和 y，长度均为 n。你必须选择三个 不同 的下标 i ，j 和 k，满足以下条件：

  • x[i] != x[j]
  • x[j] != x[k]
  • x[k] != x[i]

你的目标是在满足这些条件下 最大化 y[i] + y[j] + y[k] 的值。返回通过选择这样一组三元组下标所能获得的 最大 可能和。

如果不存在这样的三元组，返回 -1。

 

示例 1：

输入：x = [1,2,1,3,2], y = [5,3,4,6,2]

输出：14

解释：

  • 选择 i = 0（x[i] = 1，y[i] = 5），j = 1（x[j] = 2，y[j] = 3），k = 3（x[k] = 3，y[k] = 6）。
  • 选出的三个 x 中的值互不相同。5 + 3 + 6 = 14 是我们能获得的最大值。因此输出为 14。

示例 2：

输入：x = [1,2,1,2], y = [4,5,6,7]

输出：-1

解释：

  • x 中只有两个不同的值。因此输出为 -1。

 

提示：

  • n == x.length == y.length
  • 3 <= n <= 105
  • 1 <= x[i], y[i] <= 106

解法

方法一：排序 + 贪心 + 哈希表

我们将数组 \(x\) 和 \(y\) 中的元素配对成一个二维数组 \(\textit{arr}\)，然后按照 \(y\) 的值从大到小对 \(\textit{arr}\) 进行排序。接下来，我们使用一个哈希表来记录已经选择的 \(x\) 值，并遍历 \(\textit{arr}\)，每次选择一个未被选择的 \(x\) 值和对应的 \(y\) 值，直到选择了三个不同的 \(x\) 值为止。

如果在遍历过程中选择了三个不同的 \(x\) 值，则返回这三个 \(y\) 值的和；如果遍历结束后仍未选择三个不同的 \(x\) 值，则返回 -1。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(\textit{x}\) 和 \(\textit{y}\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:
        arr = [(a, b) for a, b in zip(x, y)]
        arr.sort(key=lambda x: -x[1])
        vis = set()
        ans = 0
        for a, b in arr:
            if a in vis:
                continue
            vis.add(a)
            ans += b
            if len(vis) == 3:
                return ans
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maxSumDistinctTriplet(int[] x, int[] y) {
        int n = x.length;
        int[][] arr = new int[n][0];
        for (int i = 0; i < n; i++) {
            arr[i] = new int[] {x[i], y[i]};
        }
        Arrays.sort(arr, (a, b) -> b[1] - a[1]);
        int ans = 0;
        Set<Integer> vis = new HashSet<>();
        for (int i = 0; i < n; ++i) {
            int a = arr[i][0], b = arr[i][1];
            if (vis.add(a)) {
                ans += b;
                if (vis.size() == 3) {
                    return ans;
                }
            }
        }
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxSumDistinctTriplet(vector<int>& x, vector<int>& y) {
        int n = x.size();
        vector<array<int, 2>> arr(n);
        for (int i = 0; i < n; ++i) {
            arr[i] = {x[i], y[i]};
        }
        ranges::sort(arr, [](auto& a, auto& b) {
            return b[1] < a[1];
        });
        int ans = 0;
        unordered_set<int> vis;
        for (int i = 0; i < n; ++i) {
            int a = arr[i][0], b = arr[i][1];
            if (vis.insert(a).second) {
                ans += b;
                if (vis.size() == 3) {
                    return ans;
                }
            }
        }
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func maxSumDistinctTriplet(x []int, y []int) int {
    n := len(x)
    arr := make([][2]int, n)
    for i := 0; i < n; i++ {
        arr[i] = [2]int{x[i], y[i]}
    }
    sort.Slice(arr, func(i, j int) bool {
        return arr[i][1] > arr[j][1]
    })
    ans := 0
    vis := make(map[int]bool)
    for i := 0; i < n; i++ {
        a, b := arr[i][0], arr[i][1]
        if !vis[a] {
            vis[a] = true
            ans += b
            if len(vis) == 3 {
                return ans
            }
        }
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function maxSumDistinctTriplet(x: number[], y: number[]): number {
    const n = x.length;
    const arr: [number, number][] = [];
    for (let i = 0; i < n; i++) {
        arr.push([x[i], y[i]]);
    }
    arr.sort((a, b) => b[1] - a[1]);
    const vis = new Set<number>();
    let ans = 0;
    for (let i = 0; i < n; i++) {
        const [a, b] = arr[i];
        if (!vis.has(a)) {
            vis.add(a);
            ans += b;
            if (vis.size === 3) {
                return ans;
            }
        }
    }
    return -1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn max_sum_distinct_triplet(x: Vec<i32>, y: Vec<i32>) -> i32 {
        let n = x.len();
        let mut arr: Vec<(i32, i32)> = (0..n).map(|i| (x[i], y[i])).collect();
        arr.sort_by(|a, b| b.1.cmp(&a.1));
        let mut vis = std::collections::HashSet::new();
        let mut ans = 0;
        for (a, b) in arr {
            if vis.insert(a) {
                ans += b;
                if vis.len() == 3 {
                    return ans;
                }
            }
        }
        -1
    }
}

评论