跳到主要内容

元素频率

题一、统计元素频率​

方案A、通过对象​

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);

方案B、通过Map​

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

题二、多数元素​

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

示例1:

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

示例2:

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

方案A、排序法​

思路: 由于数组中总是存在多数元素，如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 n/2 的元素（下标从 0 开始）一定是众数。

  • 通过快速排序算法对数组排序
  • 返回排序后的 nums[Math.floor(nums.length/2)]
function quickSort(nums,start,end){
    if(start>=end){
        return;
    }
    let left=start;
    let right=end;
    let pivot=nums[Math.floor((left+right)/2)];
    while(left<=right){
        while(nums[left]<pivot){
            left++;
        }
        while(nums[right]>pivot){
            right--;
        }
        if(left<=right){
            [nums[left],nums[right]]=[nums[right],nums[left]];
            left++;
            right--;
        }
    }
    quickSort(nums,start,right);
    quickSort(nums,left,end);
}
function majorityElement(nums) {
    quickSort(nums,0,nums.length-1);
    return nums[Math.floor(nums.length/2)]
};

性能分析:

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(1)

方案B、Map 法​

思路:遍历整个数组，对记录每个数值出现的次数(利用HashMap，其中key为数值，value为出现次数)； 接着遍历HashMap中的每个Entry，寻找value值> nums.length / 2的key即可。

 function majorityElement(nums) {
    const map=nums.reduce((prev,curr)=>prev.set(curr,(prev.get(curr)||0)+1),new Map())
    for(let item of map){
        if(item[1]>Math.floor(nums.length/2)){
            return item[0]
        }
    }
};

性能分析:

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

摩尔投票算法​

思路:如果我们把众数记为 +1，把其他数记为 -1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

Boyer-Moore 算法的详细步骤：

  • 我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
  • 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
    • 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
    • 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
  • 在遍历完成后，candidate 即为整个数组的众数。
 function majorityElement(nums) {
    let count=0;
    let candidate;
    for(let item of nums){
        if(count==0){
            candidate=item;
        }
        count += (item == candidate) ? 1 : -1;
    }
    return candidate;
 }

性能分析:

  • 时间复杂度：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 。