1207. 独一无二的出现次数

🟢   🔖  数组 哈希表  🔗 力扣 LeetCode

题目

Given an array of integers arr, return true _if the number of occurrences of each value in the array isunique or _false otherwise.

Example 1:

Input: arr = [1,2,2,1,1,3]

Output: true

Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

Example 2:

Input: arr = [1,2]

Output: false

Example 3:

Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]

Output: true

Constraints:

• 1 <= arr.length <= 1000
• -1000 <= arr[i] <= 1000

题目大意

给你一个整数数组 arr，如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例 1：

输入： arr = [1,2,2,1,1,3]

输出： true

解释： 在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

示例 2：

输入： arr = [1,2]

输出： false

示例 3：

输入： arr = [-3,0,1,-3,1,1,1,-3,10,0]

输出： true

提示：

• 1 <= arr.length <= 1000
• -1000 <= arr[i] <= 1000

解题思路

1. 使用 Map 统计频率：

   • 遍历数组 arr，对每个元素的出现次数进行统计，存入 Map 中。键是元素，值是该元素的出现次数。

2. 检查频率的唯一性：

   • 将 Map 的值（即每个元素的出现次数）存入一个 Set 中，由于 Set 的特性，重复的值会被自动过滤。
   • 比较 Set 的大小和 Map 的大小，如果两者大小相同，则说明所有出现次数是唯一的。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度，需要遍历数组。
• 空间复杂度：O(n)，使用了额外的空间来存储频率对象和集合，最坏情况下它们的空间复杂度为 O(n)。

代码

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var uniqueOccurrences = function (arr) {
	let map = new Map();
	// 统计每个元素的出现次数
	for (let num of arr) {
		map.set(num, (map.get(num) || 0) + 1);
	}
	// 检查频率是否唯一
	return new Set(map.values()).size == map.size;
};