169.多数元素

题目描述题解(摩尔投票算法)思路代码classSolution{publicintmajorityElement(int[]nums){intcandidatenums[0];intcount0;for(intnum:nums){// 当计数器归零时更换候选人if(count0){candidatenum;}// 相同则票数 1不同则票数 -1count(numcandidate)?1:-1;}returncandidate;}}复杂度分析时间复杂度O(n)O(n)O(n)只需要对数组进行一次遍历因此时间复杂度是线性的。空间复杂度O(1)O(1)O(1)只使用了两个局部变量 candidate 和 count没有占用任何额外的数组或集合空间。