JavaScript 求解多数元素的两种算法实现

题目：多数元素

给定一个大小为 n 的数组 nums，需要返回其中的多数元素。多数元素的定义是其在数组中出现的次数严格大于 ⌊ n/2 ⌋。

题目假设输入的数组非空，且保证给定的数组中一定存在这样的多数元素。

示例 1：

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

示例 2：

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

提示：

n == nums.length

1 <= n <= 5 * 104

-109 <= nums[i] <= 109

解：

方法一：利用 Map 实现

该方法通过一次遍历，使用 Map 存储每个元素及其出现的次数。由于 Map 键的唯一性，可以准确记录频率。随后再次遍历 Map 找出出现次数大于数组长度一半的元素。第一次遍历 Map 的时间复杂度为 O(1)（单次操作），第二次遍历所有键值对的时间复杂度为 O(n)，因此总体时间复杂度为 O(n)。然而，由于需要额外开辟一个 Map 来存储数据，空间复杂度同样为 O(n)。

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let map = new Map()
    for(let i=0;i<nums.length;i++){
        if(map.has(nums[i])){
            map.set(nums[i],map.get(nums[i])+1)
        }else{
           map.set(nums[i],1)
        }
    }

    for(let [key,val] of map.entries()){
        if(val>nums.length/2){
            return key
        }
    }
};

方法二：排序法

思路：对数组进行排序。如果存在一个数字的出现频率大于 n/2，那么排序后数组中间位置（即索引为 nums.length / 2 的位置）的元素必然是该多数元素。

复杂度分析：时间复杂度为 O(nlogn)，主要取决于排序算法（如快速排序）的时间开销。空间复杂度为 O(logn)，这是排序过程中递归栈所需的额外空间。

var majorityElement = function (nums) {
    nums.sort((a, b) => a - b);
    return nums[Math.floor(nums.length / 2)];
};

以上就是前端JavaScript多数元素的算法详解的详细内容，更多关于JavaScript多数元素算法的资料请关注本站其它相关文章！