题目描述

给你一个整数数组 arr,请你帮忙统计数组中每个数的出现次数.如果每个数的出现次数都是独一无二的,就返回 true;否则返回 false

题目分析

整数数组
独一无二

参数说明

/**
 * @param {number[]} arr
 * @return {boolean}
 */

题解及实现

1.先 sort 再遍历

新建 hashMap 存储某一次数是否出现,sort 数组,将相同的元素放到一起,从头遍历,并计数,当出现新元素时,将前一个元素的出现次数放进 hashMap,依此类推,以后放之前先看下有没有

var uniqueOccurrences = function (arr) {
  let hashMap = new Map();
  arr.sort();
  let j = 0;
  let cnt = 0;
  let len = arr.length;
  while (j < len) {
    while (arr[j] === arr[j + cnt]) cnt++;
    if (hashMap.get(cnt)) return false;
    hashMap.set(cnt, 1);
    j += cnt;
    cnt = 0;
  }
  return true;
};

时间复杂度:O(nlog(n))

资源使用情况
- 执行用时：84 ms, 在所有 JavaScript 提交中击败了 75.14%的用户
- 内存消耗：37.9 MB, 在所有 JavaScript 提交中击败了 41.93%的用户

同思路希尔排序版
考虑到相同元素出现较多,可用希尔排序将他们快速放在一起

var uniqueOccurrences = function (arr) {
  let hashMap = new Map();
  arr = shellSort(arr);
  let j = 0;
  let cnt = 0;
  let len = arr.length;
  while (j < len) {
    while (arr[j] === arr[j + cnt]) cnt++;
    if (hashMap.get(cnt)) return false;
    hashMap.set(cnt, 1);
    j += cnt;
    cnt = 0;
  }
  return true;
};
function shellSort(arr = []) {
  let len = arr.length;
  let gap;
  for (gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < len; ++i) {
      let current = arr[i];
      let j = i;
      while (j - gap >= 0 && current < arr[j - gap]) {
        arr[j] = arr[j - gap];
        j = j - gap;
      }
      arr[j] = current;
    }
  }
  return arr;
}

资源使用情况
- 执行用时：76 ms, 在所有 JavaScript 提交中击败了 94.05%的用户
- 内存消耗：38.1 MB, 在所有 JavaScript 提交中击败了 41.29%的用户

2.Set 和 Map

用 Map 记录出现的次数,再把次数放到 Set,看数量有没有变化

var uniqueOccurrences = function (arr) {
  let myMap = new Map();
  let mySet = new Set();
  for (num of arr) {
    if (!myMap.get(num)) myMap.set(num, 1);
    else myMap.set(num, myMap.get(num) + 1);
  }
  for (val of myMap.values()) {
    mySet.add(val);
  }
  return myMap.size === mySet.size;
};

时间复杂度:O(n)

资源使用情况
- 执行用时：76 ms, 在所有 JavaScript 提交中击败了94.05%的用户
- 内存消耗：39 MB, 在所有 JavaScript 提交中击败了22.58%的用户
  问题:空间消耗大

2020-10-28 独一无二的出现次数