LeetCode.1207-唯一的元素出现次数(Unique Number of Occurrences)
这是小川的第419次更新，第452篇原创
看题和准备
今天介绍的是LeetCode算法题中Easy级别的第269题（顺位题号是1207）。给定一个整数数组arr，当且仅当该数组中每个元素的出现次数唯一时，返回true。
例如：
输入：arr = [1,2,2,1,1,3]
输出：true
说明：值1出现3次，值2出现2次，值3出现1次。没有两个值出现的次数相同。
输入：arr = [1,2]
输出：false
输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true
限制条件：
- 1 <= arr.length <= 1000
- -1000 <= arr[i] <= 1000
第一种解法
题目的意思是判断数组中的元素的出现次数是否唯一，我们可以直接使用HashMap和HashSet结合，先遍历arr中的元素，将元素值作为key，出现次数作为value存入HashMap中，再遍历HashMap的所有value，存入HashSet中，如果当前value已经存在，直接返回false。
public boolean uniqueOccurrences(int[] arr) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : arr) {
map.put(num, map.getOrDefault(num, 0)+1);
}
Set<Integer> set = new HashSet<Integer>();
for (Integer count : map.values()) {
if (set.contains(count)) {
return false;
}
set.add(count);
}
return true;
}
第二种解法
使用int数组计数。因为题目限定了原始数组的长度和元素值范围，所以我们可以借助计数来解决此问题。
第一次计数，声明一个长度为2001的int数组count，将原始数组的值加上1000后作为新数组索引。第二次计数，同样声明一个长度为2001的int数组count2，如果count中的当前元素不等于0，就将当前元素作为count2数组的索引，元素值累加，加完后判断元素值是否大于等于2，如果大于，直接返回false。
public boolean uniqueOccurrences2(int[] arr) {
int[] count = new int[2001];
for (int num : arr) {
count[num+1000]++;
}
int[] count2 = new int[2001];
for (int con : count) {
if (con != 0) {
count2[con]++;
if (count2[con] >= 2) {
return false;
}
}
}
return true;
}
第三种解法
和上面第二种解法类似，只是将第二步计数的int数组换成了boolean类型，其他思路不变。
public boolean uniqueOccurrences3(int[] arr) {
int[] count = new int[2001];
for (int num : arr) {
count[num+1000]++;
}
boolean[] flag = new boolean[2001];
for (int con : count) {
if (con > 0) {
if (flag[con]) {
return false;
} else {
flag[con] = true;
}
}
}
return true;
}
小结
算法专题目前已更新LeetCode算法题文章275+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、在看就是对我最大的回报和支持！
最新文章
- iBatis简单入门教程
- 从service弹出系统级自定义提示框，可在任意页面弹出
- LeetCode:Best Time to Buy and Sell Stock I II III
- [转载] linux cgroup
- Maven Project configuration is not up-to-date with pom.xml错误解决方法
- 纯java从apk文件里获取包名、版本号、icon
- mysql存储过程出现OUT or INOUT argument 10 for routine
- 查看ORACLE执行计划的几种常用方法
- ClassLoader类加载解惑
- kafka使用实例
- while循环 操作列表与字典
- python爬虫——写出最简单的网页爬虫
- angularjs MVC、模块化、依赖注入详解
- python 常用镜像
- ubuntu 开发环境配置及安装 nodejs
- jpa 分页
- mysql ----BaseDao工具类
- linux学习：【第1篇】初识Linux及安装
- ubuntu16.04 下 卸载CUDA9.1
- 清除浮动以及:after元素