JAVA练习324- 多数元素

题目概览给定一个大小为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) 的算法解决此问题。来源169. 多数元素 - 力扣LeetCode解题分析方法摩尔投票由于多数元素在数组中出现次数大于⌊ n/2 ⌋假设该元素为 1其余元素为 -1全部元素相加之后一定是大于 0 的我们可以称这个为票数。因此我们定义一个变量 res当票数之和为 0 时就将 res 设置为新元素当数组遍历完成时res 一定是多数元素。时间复杂度O(n)空间复杂度O(1)class Solution { public int majorityElement(int[] nums) { int res 0, vote 0; for (int num: nums) { if (vote 0) { res num; } vote (res num ? 1: -1); } return res; } }