力扣面试经典150题-169. 多数元素

文章目录题目**暴力解****Boyer-Moore 投票算法**题目给定一个大小为 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) 的算法解决此问题。补全以下代码classSolution{publicintmajorityElement(int[]nums){}}题目意思应该是找出传入数组的多数元素一个因为返回的是一个int类型且题目要求返回传入数组中的多数元素暴力解先排序因为多数元素个数大于总个数/2因此多数元素一定占了最中间位置classSolution{publicintmajorityElement(int[]nums){Arrays.sort(nums);returnnums[nums.length/2];}}Boyer-Moore 投票算法维护一个候选元素candidate和计数器count遍历数组若count0将当前元素设为候选若当前元素等于候选count加1否则count减1由于多数元素出现次数超过一半最终留下的候选必定是多数元素可以分为两种情况若第一个为多数元素若第一个不为多数元素但count最后一次变为0一定是因为多数元素的出现classSolution{publicintmajorityElement(int[]nums){intcandidate0;intcount0;for(intnum:nums){//第一个是否为多数元素不重要if(count0){candidatenum;}/*多数元素出现次数超过一半 count最后一次为0时一定是因为多数元素的出现*/count(numcandidate)?1:-1;}returncandidate;}}