题目
题目
分析
最开始思路:排序,然后取nums[n/2]
,但是时间复杂度不过关。
摩尔投票法,学到了!
代码
class Solution {
public:int majorityElement(vector<int>& nums) {int cnt=0;int target_num=nums[0];for(int i=1;i<nums.size();i++){if(nums[i]==target_num)cnt++;elsecnt--;if(cnt==-1){target_num=nums[i];cnt=0;}}return target_num;}};