跳转至

3631. 按严重性和可利用性排序威胁 🔒

题目描述

给定一个二维整数数组 threats，其中 threats[i] = [IDi, sevi​, expi]。

  • IDi：威胁的唯一标识。
  • sevi：表示威胁的严重程度。
  • expi：表示威胁的可利用性。

威胁 i 的 分数 定义为：score = 2 × sevi + expi

你的任务是按 分数降序 返回 threats。

如果多个威胁具有相同的分数，则按 ID 升序 排序。

 

示例 1：

输入：threats = [[101,2,3],[102,3,2],[103,3,3]]

输出：[[103,3,3],[102,3,2],[101,2,3]]

解释：

威胁 ID sev exp 分数 = 2 × sev + exp
threats[0] 101 2 3 2 × 2 + 3 = 7
threats[1] 102 3 2 2 × 3 + 2 = 8
threats[2] 103 3 3 2 × 3 + 3 = 9

排序顺序：[[103, 3, 3], [102, 3, 2], [101, 2, 3]]

示例 2：

输入：threats = [[101,4,1],[103,1,5],[102,1,5]]

输出：[[101,4,1],[102,1,5],[103,1,5]]

解释：

威胁 ID sev exp 分数 = 2 × sev + exp
threats[0] 101 4 1 2 × 4 + 1 = 9
threats[1] 103 1 5 2 × 1 + 5 = 7
threats[2] 102 1 5 2 × 1 + 5 = 7

threats[1] 与 threats[2] 有相同的分数，因此它们按升序排序。

排序顺序：[[101, 4, 1], [102, 1, 5], [103, 1, 5]]

 

提示：

  • 1 <= threats.length <= 105
  • threats[i] == [IDi, sevi, expi]
  • 1 <= IDi <= 106
  • 1 <= sevi <= 109
  • 1 <= expi <= 109
  • 所有 IDi 互不相同。

解法

方法一：排序

我们直接按照题目要求的方式对数组进行排序即可。需要注意的是，分数是一个长整型数，因此在比较时需要使用长整型来避免溢出。

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

1
2
3
4
class Solution:
    def sortThreats(self, threats: List[List[int]]) -> List[List[int]]:
        threats.sort(key=lambda x: (-(x[1] * 2 + x[2]), x[0]))
        return threats

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int[][] sortThreats(int[][] threats) {
        Arrays.sort(threats, (a, b) -> {
            long score1 = 2L * a[1] + a[2];
            long score2 = 2L * b[1] + b[2];
            if (score1 == score2) {
                return Integer.compare(a[0], b[0]);
            }
            return Long.compare(score2, score1);
        });
        return threats;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<vector<int>> sortThreats(vector<vector<int>>& threats) {
        sort(threats.begin(), threats.end(), [](const vector<int>& a, const vector<int>& b) {
            long long score1 = 2LL * a[1] + a[2];
            long long score2 = 2LL * b[1] + b[2];
            if (score1 == score2) {
                return a[0] < b[0];
            }
            return score2 < score1;
        });
        return threats;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func sortThreats(threats [][]int) [][]int {
    sort.Slice(threats, func(i, j int) bool {
        score1 := 2*int64(threats[i][1]) + int64(threats[i][2])
        score2 := 2*int64(threats[j][1]) + int64(threats[j][2])
        if score1 == score2 {
            return threats[i][0] < threats[j][0]
        }
        return score2 < score1
    })
    return threats
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function sortThreats(threats: number[][]): number[][] {
    threats.sort((a, b) => {
        const score1 = 2 * a[1] + a[2];
        const score2 = 2 * b[1] + b[2];
        if (score1 === score2) {
            return a[0] - b[0];
        }
        return score2 - score1;
    });
    return threats;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn sort_threats(mut threats: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        threats.sort_by(|a, b| {
            let score1 = 2i64 * a[1] as i64 + a[2] as i64;
            let score2 = 2i64 * b[1] as i64 + b[2] as i64;
            if score1 == score2 {
                a[0].cmp(&b[0])
            } else {
                score2.cmp(&score1)
            }
        });
        threats
    }
}

评论