离散化——unordered_map

2024-06-13 04:18
文章标签 map unordered 离散

本文主要是介绍离散化——unordered_map,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

学习一下unordered_map的用法,上海区域赛前才第一次见这个东西,看到和map用法一样自信觉得能用,然而场上卡住了,现在滚过来学一下orz【虽然事后发现G题根本不需要用这个东西。

学过哈希的都很容易理解离散化,无非就是数据过大开不了那么大的数组时,但其实中间有很多浪费掉的空间,那么映射到另一个数组中就可以了。

以前常用的c++离散化是

// a[i] 为初始数组,下标范围为 [1, n]
// len 为离散化后数组的有效长度
std::sort(a + 1, a + 1 + n);len = std::unique(a + 1, a + n + 1) - a - 1;
// 离散化整个数组的同时求出离散化后本质不同数的个数。
std::lower_bound(a + 1, a + len + 1, x) - a;  // 查询 x 离散化后对应的编号

而unordered_map是一个内部实现了哈希表的数据结构。其查找效率是O(1)的。

那么先上一个基础应用例题:https://ac.nowcoder.com/acm/contest/5158/H

在这里插入图片描述

明显并查集,但是1e9,这么大肯定离散化,那就用一下这个unordered_map代替并查集中的pre数组就ok

#include<bits/stdc++.h>
using namespace std;
unordered_map<int ,int > pre;int find(int a)
{if(pre[a] == 0)return a;elsereturn pre[a] = find(pre[a]); 
}void Union(int a,int b){int m = find(a);int n = find(b);pre[m] = n;return ;
}int main()
{cin.tie(0),ios::sync_with_stdio(false);int t;cin>>t;while(t--) {pre.clear();int flag = 1;int n,a,b,c;cin >> n;for(int i = 0 ;i < n; i++) {cin>>a>>b>>c;int m = find(a);int n = find(b);if(c == 1 ){if( m!=n && a !=m &&b != n){flag = 0;break;}else Union(a,b);}else{if( m == n){flag = 0;break;}      }}if(flag == 0)cout<<"NO"<<endl;elsecout<<"YES"<<endl;}system("pause");return 0;
}

未完持续考完试继续写

这篇关于离散化——unordered_map的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1056252

相关文章

Java中Map.Entry()含义及方法使用代码

《Java中Map.Entry()含义及方法使用代码》:本文主要介绍Java中Map.Entry()含义及方法使用的相关资料,Map.Entry是Java中Map的静态内部接口,用于表示键值对,其... 目录前言 Map.Entry作用核心方法常见使用场景1. 遍历 Map 的所有键值对2. 直接修改 Ma

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》:本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时,需要提供方将Map类型的数据序列化为co

Java使用Stream流的Lambda语法进行List转Map的操作方式

《Java使用Stream流的Lambda语法进行List转Map的操作方式》:本文主要介绍Java使用Stream流的Lambda语法进行List转Map的操作方式,具有很好的参考价值,希望对大... 目录背景Stream流的Lambda语法应用实例1、定义要操作的UserDto2、ListChina编程转成M

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》:本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v

Golang中map缩容的实现

《Golang中map缩容的实现》本文主要介绍了Go语言中map的扩缩容机制,包括grow和hashGrow方法的处理,具有一定的参考价值,感兴趣的可以了解一下... 目录基本分析带来的隐患为什么不支持缩容基本分析在 Go 底层源码 src/runtime/map.go 中,扩缩容的处理方法是 grow

Go语言利用泛型封装常见的Map操作

《Go语言利用泛型封装常见的Map操作》Go语言在1.18版本中引入了泛型,这是Go语言发展的一个重要里程碑,它极大地增强了语言的表达能力和灵活性,本文将通过泛型实现封装常见的Map操作,感... 目录什么是泛型泛型解决了什么问题Go泛型基于泛型的常见Map操作代码合集总结什么是泛型泛型是一种编程范式,允

JSON字符串转成java的Map对象详细步骤

《JSON字符串转成java的Map对象详细步骤》:本文主要介绍如何将JSON字符串转换为Java对象的步骤,包括定义Element类、使用Jackson库解析JSON和添加依赖,文中通过代码介绍... 目录步骤 1: 定义 Element 类步骤 2: 使用 Jackson 库解析 jsON步骤 3: 添

Java中List转Map的几种具体实现方式和特点

《Java中List转Map的几种具体实现方式和特点》:本文主要介绍几种常用的List转Map的方式,包括使用for循环遍历、Java8StreamAPI、ApacheCommonsCollect... 目录前言1、使用for循环遍历:2、Java8 Stream API:3、Apache Commons