义乌城市投资建设集团网站,深圳专业建站公司有哪些,wordpress 公式编辑器,织梦网站怎样入侵这道题如果不考虑空间复杂度和时间复杂度的限制的话很好做#xff0c;一种思路是通过一次遍历将所有元素的数量记录在一个哈希表中#xff0c;然后我们直接返回出现次数最多的键即可。另一种思路是直接对数组进行排序#xff0c;数组中间的值一定是多数元素#xff0c;因为… 这道题如果不考虑空间复杂度和时间复杂度的限制的话很好做一种思路是通过一次遍历将所有元素的数量记录在一个哈希表中然后我们直接返回出现次数最多的键即可。另一种思路是直接对数组进行排序数组中间的值一定是多数元素因为该元素超过半数在有序的状态下无论如何都会在数组的中间位置出现这个也很好想。 但是考虑时间和空间的限制这道题就很难想了这道题我是看了华南溜达虎的视频才做出来的感觉他对摩尔投票法讲解的还不错也可以结合K神的题解来看更加通俗易懂。 我们定义count和resultresult代表多数元素而count对应多数元素的数量初始化为0我们先假定nums[0]为多数元素遍历整个数组nums当nums[i] result时我们将当前多数元素的数量1然后遍历下一个元素当nums[i] ! result时我们就将count减一当count被减为负数时说明当前认定的多数元素可能不是真正的多数元素我们将result赋值为当前的nums[i]并将count赋值为1对应当前多数元素的数量 经历过一次遍历后由于多数的数量超过半数至少比其他的元素个数之和多1无论数组如何排列最后一定是多数的票数占优最后result一定会被赋值为多数。
class Solution {
public:int majorityElement(vectorint nums) {int count 0;int result nums[0];for(int i 0; i nums.size(); i){if(nums[i] result)count;else{count--;if(count 0){result nums[i];count 1;} }}return result;}
};
