C/C++哈希表优化LeetCode题解997找到小镇的法官

目录
  • 方法一、哈希表
  • 方法二、优化

方法一、哈希表

今天这道题比较简单，我们可以统计每个人信任别人的数量和被信任的数量，如果存在某个人信任别人的数量为0，且被信任的数量为 n-1，那么，这个人就是法官。

因为本题的数据范围为 [1,1000]，数据范围比较小，所以，直接使用数组作为哈希表来使用。

请看代码：

class Solution {
    public int findJudge(int n, int[][] trust) {
        // 不信任任何人的人 & 被所有人信任的人
        // 计算每个人信任的人的数量和被信任的数量
        // 前者等于0，后者等于n-1
        int[][] arr = new int[n + 1][2];
        for (int[] t : trust) {
            // 0表示信任别人
            arr[t[0]][0]++;
            // 1表示被别人信任
            arr[t[1]][1]++;
        }

        for (int i = 1; i <= n; i++) {
            if (arr[i][0] == 0 && arr[i][1] == n - 1) {
                return i;
            }
        }
                return -1;
    }
}
  • 时间复杂度：O(m)，m 为 trust 数组的长度。
  • 空间复杂度：O(n)。

运行结果如下：

方法二、优化

方法一中，我们使用了一个二维数组的第二维表示信任别人的数量和被别人信任的数量，其实，我们也可以使用一个一维数组来求解， 减一表示信任别人的数量，加一表示被别人信任的数量，那么，只有法官才可能达到 n-1 的总数量。

请看代码：

class Solution {
    public int findJudge(int n, int[][] trust) {
        // 不信任任何人的人 & 被所有人信任的人
        int[] arr = new int[n + 1];
        for (int[] t : trust) {
            // 减一表示信任别人
            arr[t[0]]--;
            // 加一表示被别人信任
            arr[t[1]]++;
        }

        for (int i = 1; i <= n; i++) {
            // 因为被别人信任不可能超过 n-1
            // 所以，只有法官能达到 n-1
            // 且法官信任别人数量为 0
            // 所以，总的数量为 n-1
            if (arr[i] == n - 1) {
                return i;
            }
        }
                return -1;
    }
}
  • 时间复杂度：O(m)，m 为 trust 数组的长度。
  • 空间复杂度：O(n)。

以上就是C/C++哈希表优化LeetCode题解997找到小镇的法官的详细内容，更多关于C/C++哈希表优化找到小镇法官的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C++ LeetCode1769移动所有球到每个盒子最小操作数示例

    目录 LeetCode 1769.移动所有球到每个盒子所需的最小操作数 方法一:数学思维 AC代码 C++ LeetCode 1769.移动所有球到每个盒子所需的最小操作数 力扣题目链接:leetcode.cn/problems/mi… 有 n 个盒子.给你一个长度为 n 的二进制字符串 boxes ,其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的,而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球. 在一步操作中,你可以将 一个 小球从某个盒子移动到一个与之相

  • C++ LeetCode1796字符串中第二大数字

    目录 LeetCode 1796.字符串中第二大的数字 方法一:遍历 题目分析 解题思路 复杂度分析 AC代码 C++ LeetCode 1796.字符串中第二大的数字 力扣题目链接:leetcode.cn/problems/se… 给你一个混合字符串 s ,请你返回 s 中 第二大 的数字,如果不存在第二大的数字,请你返回 -1 . 混合字符串 由小写英文字母和数字组成. 示例 1: 输入:s = "dfa12321afd"输出:2解释:出现在 s 中的数字包括 [1, 2, 3]

  • C++ LeetCode542矩阵示例详解

    目录 LeetCode  542.01 矩阵 方法一:广度优先搜索 AC代码 C++ LeetCode  542.01 矩阵 力扣题目链接:leetcode.cn/problems/01… 给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离. 两个相邻元素间的距离为 1 . 示例 1: 输入:mat = [[0,0,0],[0,1,0],[0,0,0]]输出:[[0,0,0],[0,1,0],[0,0,0]] 示例

  • C++ LeetCode1805字符串不同整数数目

    目录 LeetCode 1805.字符串中不同整数的数目 方法一:遍历拆分 AC代码 C++ LeetCode 1805.字符串中不同整数的数目 力扣题目链接:leetcode.cn/problems/nu… 给你一个字符串 word ,该字符串由数字和小写英文字母组成. 请你用空格替换每个不是数字的字符.例如,"a123bc34d8ef34" 将会变成 " 123  34 8  34" .注意,剩下的这些整数为(相邻彼此至少有一个空格隔开):"123&q

  • C++ LeetCode543题解二叉树直径

    目录 LeetCode 543.二叉树的直径 方法一:深度优先搜索求二叉树的深度 AC代码 C++ LeetCode 543.二叉树的直径 力扣题目链接:leetcode.cn/problems/di… 给定一棵二叉树,你需要计算它的直径长度.一棵二叉树的直径长度是任意两个结点路径长度中的最大值.这条路径可能穿过也可能不穿过根结点. 示例 :给定二叉树 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]. 注意:两结点之间的路径长度是以它们之间边的数目表示. 方法一:深度优

  • C/C++哈希表优化LeetCode题解997找到小镇的法官

    目录 方法一.哈希表 方法二.优化 方法一.哈希表 今天这道题比较简单,我们可以统计每个人信任别人的数量和被信任的数量,如果存在某个人信任别人的数量为0,且被信任的数量为 n-1,那么,这个人就是法官. 因为本题的数据范围为 [1,1000],数据范围比较小,所以,直接使用数组作为哈希表来使用. 请看代码: class Solution { public int findJudge(int n, int[][] trust) { // 不信任任何人的人 & 被所有人信任的人 // 计算每个人信任

  • Go/C语言LeetCode题解997找到小镇法官

    目录 题目描述 思路分析 go 代码 C语言 暴力法 题目描述 997. 找到小镇的法官 - 力扣(LeetCode) 小镇里有 n 个人,按从 1 到 n 的顺序编号.传言称,这些人中有一个暗地里是小镇法官. 如果小镇法官真的存在,那么: 小镇法官不会信任任何人. 每个人(除了小镇法官)都信任这位小镇法官. 只有一个人同时满足属性 1 和属性 2 . 给你一个数组 trust ,其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人. 如果小镇法官存在并且可

  • Go语言LeetCode题解706设计哈希映射

    目录 题目描述 思路分析 AC 代码 题目描述 706. 设计哈希映射 不使用任何内建的哈希表库设计一个哈希映射(HashMap). 实现 MyHashMap 类: MyHashMap() 用空映射初始化对象 void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) .如果 key 已经存在于映射中,则更新其对应的值 value . int get(int key) 返回特定的 key 所映射的 value :如果映射中不包含 key

  • C++中的数组、链表与哈希表

    C++中的数组、链表与哈希表

    目录 数组和链表 数组 链表 什么是链表? 链表的操作 双向链表(list) list的成员函数 哈希表 什么是哈希表? 哈希碰撞 哈希表应用场景 构建哈希表 哈希表基本使用 Leetcode对应题目 前缀和 差分数组 滑动窗口 二分查找 数组和链表 C++的数组和链表分别是什么?分别有什么种类?它们都有什么特性?针对这些特征,使用情形是什么? 数组 什么是数组? 一个数组就像是一个变量,它可以存储一组值,但是所有值都是相同的数据类型. 一个int数组定义:int hours [6] 该数组类型

  • Go语言leetcode题解953验证外星语词典示例详解

    目录 题目描述 思路分析 AC 代码 题目描述 953. 验证外星语词典 某种外星语也使用英文小写字母,但可能顺序 order 不同.字母表的顺序(order)是一些小写字母的排列. 给定一组用外星语书写的单词 words,以及其字母表的顺序 order,只有当给定的单词在这种外星语中按字典序排列时,返回 true:否则,返回 false. 示例 1: 输入:words = ["hello","leetcode"], order = "hlabcdefgi

  • JAVA中哈希表HashMap的深入学习

    深入浅出学Java--HashMap 哈希表(hash table) 也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,本文会对java集合框架中HashMap的实现原理进行讲解,并对JDK7的HashMap源码进行分析. 一.什么是哈希表 在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能 数组:采用一段连续的存储单元来存储数据.对于指定下标的查找,时间复杂度为O(1):通过给定值进

  • 一文彻底搞定Java哈希表和哈希冲突

    一文彻底搞定Java哈希表和哈希冲突

    一.什么是哈希表? 哈希表也叫散列表,它是基于数组的.这间接带来了一个优点:查找的时间复杂度为 O(1).当然,它的插入时间复杂度也是 O(1).还有一个缺点:数组创建后扩容成本较高. 哈希表中有一个"主流"思想:转换.一个重要的概念是将「键」或「关键字」转换成数组下标.这由"哈希函数"完成. 二.什么是哈希函数? 由上,其作用就是将非 int 的键/关键字转化为 int 的值,使可以用来做数组下标. 比如,HashMap 中就这样实现了哈希函数: static f

  • 简单讲解哈希表

    简单讲解哈希表

    目录 一.哈希表的概念 1.查找算法 2.哈希表 3.哈希数组 4.关键字 5.哈希函数 6.哈希冲突 7.哈希地址 二.常用哈希函数 1.直接定址法 2.平方取中法 3.折叠法 4.除留余数法 5.位与法 三.常见哈希冲突解决方案 1.开放定址法 1)原理讲解 2)动画演示 2.再散列函数法 1)原理讲解 2)动画演示 3.链地址法 1)原理讲解 2)动画演示 4.公共溢出区法 1)原理讲解 2)动画演示 四.哈希表的实现 1.数据结构定义 2.哈希表初始化 3.哈希函数计算 4.哈希表查找

  • 详解JavaScript实现哈希表

    详解JavaScript实现哈希表

    目录 一.哈希表原理 二.哈希表的概念 三.哈希化冲突问题 1.链地址法 2.开放地址法 四.哈希函数的实现 五.封装哈希表 六.哈希表操作 1.插入&修改操作 2.获取操作 3.删除操作 4.判断哈希表是否为空 5.获取哈希表的元素个数 七.哈希表扩容 1.哈希表扩容思想 2.哈希表扩容实现 八.完整代码  一.哈希表原理 哈希表是一种非常重要的数据结构,几乎所有的编程语言都有直接或者间接的应用这种数据结构,它通常是基于数组实现的,当时相对于数组,它有更多的优势: 它可以提供非常快速的插入-删

  • C++中使用哈希表(unordered_map)的一些常用操作方法

    目录 1.建立基本数据类型的哈希表 2.向哈希表中添加元素 1).insert函数 2).用数组方法直接添加 3.成员函数 begin(),end()函数 find()查找函数 count()查找函数 size()函数 empty()函数 clear()函数 swap()函数 哈希表的遍历 第一种遍历 第二种遍历 补充:实际应用 总结 1.建立基本数据类型的哈希表 unordered_map<int,int> m; //<string,string>,<char,char&g

随机推荐