python 做下载网站,哈尔滨网站开发需要多少钱,安阳市最新消息,北京建筑设计院待遇好吗169. 多数元素
简单
相关标签
相关企业
给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。 示例 1#xff1a;
输入#xff…169. 多数元素
简单
相关标签
相关企业
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。 示例 1
输入nums [3,2,3]
输出3
示例 2
输入nums [2,2,1,1,1,2,2]
输出2提示
n nums.length1 n 5 * 104-109 nums[i] 109 进阶尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
关于这道题我的第一次答案如下但是显示超出时间限制因为当给出的nums容器元素数量非常多的时候需要的时间很长。
class Solution {
public:int majorityElement(vectorint nums) {int lennums.size();for(int j0;jlen;j){int maxnum0;for(int i0;ilen;i){if(nums[i]nums[j])maxnum;if(maxnumlen/2)return nums[i];}}return -1;}
};
于是我进行了retry
class Solution {
public:int majorityElement(vectorint nums) {sort(nums.begin(),nums.end());int lennums.size();return nums[len/2];}
};
嘻嘻这次的想法比较标新立异我首先使用了排序因为大数是出现次数大于一半那么进行排序的时候在中间位置出现的一定是大数。
下面我们来看一看标准答案
class Solution {
public:int majorityElement(vectorint nums) {unordered_mapint,intcounts;int majority0,cnt0;for(int num:nums){counts[num];if(counts[num]cnt){majoritynum;cntcounts[num];}}return majority;}
};
使用了map映射但是明显性能不如我的排序。map的左边表示的是容器中出现的数字右边表示的是出现的次数从前往后开始遍历将元素出现的次数进行累加如果出现的次数超过一半直接返回。
当然我们也可以将答案的代码稍作修改
class Solution {
public:int majorityElement(vectorint nums) {unordered_mapint,intcounts;int lennums.size();int majority;for(int num:nums){counts[num];if(counts[num]len/2){majoritynum;}}return majority;}
};
