跳到主要内容

元素频率

一、统计元素频率​

1.1 通过对象​

const array =  [1,1,3,3,3,3,3,6,7,7,7,7,7,8,8,8,8];
const result = array.reduce(function(accumulator,currentValue,index,arr){
    if(currentValue in accumulator){
    accumulator[currentValue]++
    }else{
    accumulator[currentValue] = 1;
    }
    return accumulator;
},{});
console.log(result);

1.2 通过Map​

function countFrequency(nums){
    return nums.reduce((prev,curr)=>prev.set(curr,(prev.get(curr)||0)+1),new Map())
}

二、多数元素​

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例1:

输入：[3,2,3]
输出：3

示例2:

输入：[2,2,1,1,1,2,2]
输出：2

2.1 Boyer-Moore 投票算法​

思路: Boyer-Moore 摩尔投票思想, 算法利用票数抵消的思想, 票数为 0 时更新候选人, 每次遇到与候选人相同的数字，就增加票数, 不同的数字则减少票数。最终, 多数元素（出现次数超过 n/2 次）一定会留下正票，因此能在最后胜出。

一、初始化变量:

  • count: 用于记录当前候选元素的票数，初始为 0。

  • candidate: 用于存储当前的候选多数元素，初始为 null。

二、遍历数组: 使用 for...of 循环遍历数组中的每个数字:

  • 票数归零时更新候选人, 当票数为 0 时, 说明之前的候选人已经抵消完毕，此时将当前数字设为新的候选人。

  • 票数加减, 如果当前数字等于候选人，则票数加 1, 否则票数减 1。

三、返回结果: 遍历结束后，由于多数元素的出现次数超过一半，它最终会成为候选人，因此返回 candidate 即可。

function multiElement(nums) {
  let count = 0;
  let element = 0;

  nums.forEach((value) => {
    if (count === 0) {
      element = value;
    }

    count += element === value ? 1 : -1;
  });

  return element;
}

  • 时间复杂度: O(n)，只需要一次遍历。

  • 空间复杂度: O(1)，只使用了常数级别的额外空间。

三、最高频元素的频数​

元素的频数是该元素在一个数组中出现的次数。给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1。执行最多 k 次操作后，返回数组中最高频元素的最大可能频数。

示例1:

输入：nums = [1,2,4], k = 5
输出：3
解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。
4 是数组中最高频元素，频数是 3 。

示例2:

输入：nums = [1,4,8,13], k = 5
输出：2
解释：存在多种最优解决方案：
- 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。
- 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。
- 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。