1207.独一无二的出现次数
给你一个整数数组 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
思路
这道题目数组在是哈希法中的经典应用，如果对数组在哈希法中的使用还不熟悉的同学可以看这两篇：数组在哈希法中的应用 (opens in a new tab)和哈希法：383. 赎金信 (opens in a new tab)
进而可以学习一下set 在哈希法中的应用 (opens in a new tab)，以及map 在哈希法中的应用 (opens in a new tab)
回归本题，本题强调了-1000 <= arr[i] <= 1000，那么就可以用数组来做哈希，arr[i]作为哈希表（数组）的下标，那么 arr[i]可以是负数，怎么办？负数不能做数组下标。
此时可以定义一个 2000 大小的数组，例如 int count[2002];，统计的时候，将 arr[i]统一加 1000，这样就可以统计 arr[i]的出现频率了。
题目中要求的是是否有相同的频率出现，那么需要再定义一个哈希表（数组）用来记录频率是否重复出现过，bool fre[1002]; 定义布尔类型的就可以了，因为题目中强调 1 <= arr.length <= 1000，所以哈希表大小为 1000 就可以了。
如图所示：
C++代码如下：
class Solution {
public:
bool uniqueOccurrences(vector<int>& arr) {
int count[2002] = {0}; // 统计数字出现的频率
for (int i = 0; i < arr.size(); i++) {
count[arr[i] + 1000]++;
}
bool fre[1002] = {false}; // 看相同频率是否重复出现
for (int i = 0; i <= 2000; i++) {
if (count[i]) {
if (fre[count[i]] == false) fre[count[i]] = true;
else return false;
}
}
return true;
}
};其他语言版本
Java：
class Solution {
public boolean uniqueOccurrences(int[] arr) {
int[] count = new int[2002];
for (int i = 0; i < arr.length; i++) {
count[arr[i] + 1000]++; // 防止负数作为下标
}
boolean[] flag = new boolean[1002]; // 标记相同频率是否重复出现
for (int i = 0; i <= 2000; i++) {
if (count[i] > 0) {
if (flag[count[i]] == false) {
flag[count[i]] = true;
} else {
return false;
}
}
}
return true;
}
}Python：
# 方法 1: 数组在哈西法的应用
class Solution:
def uniqueOccurrences(self, arr: List[int]) -> bool:
count = [0] * 2002
for i in range(len(arr)):
count[arr[i] + 1000] += 1 # 防止负数作为下标
freq = [False] * 1002 # 标记相同频率是否重复出现
for i in range(2001):
if count[i] > 0:
if freq[count[i]] == False:
freq[count[i]] = True
else:
return False
return True# 方法 2： map 在哈西法的应用
class Solution:
def uniqueOccurrences(self, arr: List[int]) -> bool:
ref = dict()
for i in range(len(arr)):
ref[arr[i]] = ref.get(arr[i], 0) + 1
value_list = sorted(ref.values())
for i in range(len(value_list) - 1):
if value_list[i + 1] == value_list[i]:
return False
return True
JavaScript：
// 方法一：使用数组记录元素出现次数
var uniqueOccurrences = function (arr) {
const count = new Array(2002).fill(0); // -1000 <= arr[i] <= 1000
for (let i = 0; i < arr.length; i++) {
count[arr[i] + 1000]++; // 防止负数作为下标
}
// 标记相同频率是否重复出现
const fre = new Array(1002).fill(false); // 1 <= arr.length <= 1000
for (let i = 0; i <= 2000; i++) {
if (count[i] > 0) {
//有i出现过
if (fre[count[i]] === false)
fre[count[i]] = true; //之前未出现过，标记为出现
else return false; //之前就出现了，重复出现
}
}
return true;
};
// 方法二：使用Map 和 Set
/**
* @param {number[]} arr
* @return {boolean}
*/
var uniqueOccurrences = function (arr) {
// 记录每个元素出现次数
let map = new Map();
arr.forEach((x) => {
map.set(x, (map.get(x) || 0) + 1);
});
// Set() 里的元素是不重复的。如果有元素出现次数相同，则最后的set的长度不等于map的长度
return map.size === new Set(map.values()).size;
};TypeScript：
借用数组：
function uniqueOccurrences(arr: number[]): boolean {
const countArr: number[] = new Array(2001).fill(0);
for (let i = 0, length = arr.length; i < length; i++) {
countArr[arr[i] + 1000]++;
}
const flagArr: boolean[] = new Array(1001).fill(false);
for (let count of countArr) {
if (count === 0) continue;
if (flagArr[count] === true) return false;
flagArr[count] = true;
}
return true;
}借用 map、set
function uniqueOccurrences(arr: number[]): boolean {
const countMap: Map<number, number> = new Map();
arr.forEach((val) => {
countMap.set(val, (countMap.get(val) || 0) + 1);
});
return countMap.size === new Set(countMap.values()).size;
}Go：
func uniqueOccurrences(arr []int) bool {
count := make(map[int]int) // 统计数字出现的频率
for _, v := range arr {
count[v] += 1
}
fre := make(map[int]struct{}) // 看相同频率是否重复出现
for _, v := range count {
if _, ok := fre[v]; ok {
return false
}
fre[v] = struct{}{}
}
return true
}