企业网站的建立标准,网站开发专业就业前景,免费cms系统php,金华网站建设方案策划题目#xff1a;
给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。
方法一#xff1a;哈希表
class Solution {public int…题目
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
方法一哈希表
class Solution {public int majorityElement(int[] nums) {int n nums.length;MapInteger, Integer map new HashMap();for (int i 0; i n; i) {int times map.getOrDefault(nums[i], 0) 1;if (times (n / 2))return nums[i];map.put(nums[i], times);}return -1;}
}
时间复杂度 o( n ) 空间复杂度 o( n )
方法二摩尔投票算法 class Solution {public int majorityElement(int[] nums) {int n nums.length;int count 0, ans -1;for (int i 0; i n; i) {if (count 0) {ans nums[i];count;}else if (nums[i] ans)count;else count--;}return ans;}
}
