南宁企业建站系统,上海58同城官网,济南市莱芜区招聘信息,企业培训课程价格#x1f517;题目链接
✈题目描述#xff1a;
给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。
⌊ n/2 ⌋表示n/2结果向下取…题目链接
✈题目描述
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
⌊ n/2 ⌋表示n/2结果向下取整。
数据范围
n nums.length1 n 5 * 104-109 nums[i] 109
思路分析:
因为 ⌊ n 2 ⌋ ≤ n 2 ⌊ n 2 ⌋ 1 \lfloor \frac{n}{2} \rfloor \le \frac{n}{2} \lfloor \frac{n}{2} \rfloor 1 ⌊2n⌋≤2n⌊2n⌋1所以这个 多数元素 至多只有1个。
解法1
使用一个辅助对象计数遍历数组如果有一个元素的次数超过了 ⌊ n/2 ⌋即为结果。
/*** param {number[]} nums* return {number}*/
var majorityElement function(nums) {let count{};let flagMath.floor(nums.length/2);for(let i0;inums.length;i){if(count[nums[i]]undefined){count[nums[i]]0;}count[nums[i]];if(count[nums[i]]flag){return nums[i];}}
};时间复杂度 O ( n ) O(n) O(n)
空间复杂度 O ( n ) O(n) O(n)
解法2
由于多数元素的个数大于其他所有元素总和所以我们可以从头维护一个候选元素同时给其计数遇到同类元素1遇到异类元素-1减为0时再维护当前元素再重复之前步骤。
/*** param {number[]} nums* return {number}*/
var majorityElement function(nums) {let candidatenums[0];let count1;for(let i1;inums.length;i){if(count0){candidatenums[i];count1;}else if(candidatenums[i]){count;}else{count--;}}return candidate;
};时间复杂度 O ( n ) O(n) O(n)
空间复杂度 O ( 1 ) O(1) O(1)
