侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【图, 哈希表】道路的最大总重要性

GabrielxD
2022-05-29 / 0 评论 / 0 点赞 / 32 阅读 / 715 字 / 正在检测是否收录...

题目

6085. 道路的最大总重要性


给你一个整数 n ,表示一个国家里的城市数目。城市编号为 0n - 1

给你一个二维整数数组 roads ,其中 roads[i] = [ai, bi] 表示城市 aibi 之间有一条 双向 道路。

你需要给每个城市安排一个从 1n 之间的整数值,且每个值只能被使用 一次 。道路的 重要性 定义为这条道路连接的两座城市数值 之和 。

请你返回在最优安排下,所有道路重要性 之和 最大 为多少。

示例 1:

image-20220529024957121

输入:n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
输出:43
解释:上图展示了国家图和每个城市被安排的值 [2,4,5,3,1] 。
- 道路 (0,1) 重要性为 2 + 4 = 6 。
- 道路 (1,2) 重要性为 4 + 5 = 9 。
- 道路 (2,3) 重要性为 5 + 3 = 8 。
- 道路 (0,2) 重要性为 2 + 5 = 7 。
- 道路 (1,3) 重要性为 4 + 3 = 7 。
- 道路 (2,4) 重要性为 5 + 1 = 6 。
所有道路重要性之和为 6 + 9 + 8 + 7 + 7 + 6 = 43 。
可以证明,重要性之和不可能超过 43 。

示例 2:

image-20220529025011731

输入:n = 5, roads = [[0,3],[2,4],[1,3]]
输出:20
解释:上图展示了国家图和每个城市被安排的值 [4,3,2,5,1] 。
- 道路 (0,3) 重要性为 4 + 5 = 9 。
- 道路 (2,4) 重要性为 2 + 1 = 3 。
- 道路 (1,3) 重要性为 3 + 5 = 8 。
所有道路重要性之和为 9 + 3 + 8 = 20 。
可以证明,重要性之和不可能超过 20 。

提示:

  • 2 <= n <= 5 * 10^4
  • 1 <= roads.length <= 5 * 10^4
  • roads[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • 没有重复道路。

解题

方法一:哈希表

思路

记录每个顶点的度(countArr) ,然后按照度排序构建一个哈希表(map),键为顶点的度,因为度有可能相同,所以值为城市的数量。

遍历哈希表,度越低分配的整数值就越低,把度与分配的整数值的积加和就是重要度之和。

代码

class Solution {
    public long maximumImportance(int n, int[][] roads) {
        int[] countArr = new int[n];
        for (int[] road : roads) {
            countArr[road[0]]++;
            countArr[road[1]]++;
        }
        Map<Integer, Integer> map = new TreeMap<>();
        for (int count : countArr) {
            map.put(count, map.getOrDefault(count, 0) + 1);
        }
        long val = 1L, ans = 0L;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int count = entry.getKey(), cityCount = entry.getValue();
            while (cityCount-- > 0) {
                ans += count * val++;
            }
        }
        return ans;
    }
}

优化

class Solution {
    public long maximumImportance(int n, int[][] roads) {
        int[] degreeArr = new int[n];
        for (int[] road : roads) {
            degreeArr[road[0]]++;
            degreeArr[road[1]]++;
        }
        Arrays.sort(degreeArr);
        long value = n, ans = 0L;
        for (int i = n - 1; i >= 0; i--) {
            int degree = degreeArr[i];
            if (degree == 0) break;
            ans += degree * value--;
        }
        return ans;
    }
}
0

评论区