169. 多数元素简单给定一个大小为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) 的算法解决此问题。 核心笔记多数元素 (Majority Element - Voting Algo)1. 核心思想 (一句话总结)“极限一换一不同的数字见面就‘同归于尽’相同的数字见面就‘抱团取暖’。因为众数超过了总数的一半所以哪怕它跟所有其他异类一个个对掉最后活下来的肯定还是它。”物理意义把数组看作战场。ans是当前的擂主hp是他的兵力。抵消机制遇到同盟x ans兵力 1遇到敌人x ! ans兵力 -1相当于和一个敌人同归于尽。换人机制当兵力耗尽hp 0时说明之前的擂主已经拼光了当前的x顺势成为新擂主。2. 算法流程 (摩尔投票)初始化 (Init)ans候选众数擂主。hp血量计数器初始为 0。遍历 (Loop)判断换人如果hp 0说明之前的帐算平了或者刚开始。当前数字x登基成为新ans并将hp设为 1。判断阵营如果x ans自己人血量hp。如果x ! ans敌人互砍一刀血量hp--。结果 (Result)题目保证众数存在且所以遍历结束后ans一定是那个众数。 代码回忆清单// 题目LC 169. Majority Element class Solution { public int majorityElement(int[] nums) { int ans 0; // 当前擂主 int hp 0; // 擂主血量 (Count) for (int x : nums) { // 1. 血量归零改朝换代 // 说明之前的候选人已经被消耗殆尽了 if (hp 0) { ans x; // 新王登基 hp 1; // 初始血量 } // 2. 只有血量 0 才会走到这里 else { // 同门加血异类扣血 (一换一) hp (x ans) ? 1 : -1; } } return ans; } }⚡ 快速复习 CheckList (易错点)[ ]为什么这个算法管用它的数学本质是如果把众数记为 1其他数记为 -1。因为众数数量 所以整个数组所有元素加起来的总和一定 。不管抵消顺序如何最后剩下的只能是众数。[ ]如果众数不一定存在呢本题保证存在。如果不保证需要在得到ans后再遍历一次数组统计ans的真实出现次数确认它是否真的 。[ ]hp 0的逻辑放在哪里一定要放在循环的最开始或者每次hp变化后检查。如果是else if (hp 0)可能会漏掉处理逻辑最好写成单独的if或者像您代码中那样结构清晰的if-else。️ 数字演练nums [2, 2, 1, 1, 1, 2, 2](众数是 2)Init:ans0, hp0.x2:hp是0。换人-ans2, hp1。x2:22。加血-hp2.x1:1!2。扣血-hp1.x1:1!2。扣血-hp0. (此时 2 被两个 1 拼光了)x1:hp是0。换人-ans1, hp1. (1 暂时称王)x2:2!1。扣血-hp0. (1 被新来的 2 拼光了)x2:hp是0。换人-ans2, hp1.结束: 返回2。
169. 多数元素
169. 多数元素简单给定一个大小为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) 的算法解决此问题。 核心笔记多数元素 (Majority Element - Voting Algo)1. 核心思想 (一句话总结)“极限一换一不同的数字见面就‘同归于尽’相同的数字见面就‘抱团取暖’。因为众数超过了总数的一半所以哪怕它跟所有其他异类一个个对掉最后活下来的肯定还是它。”物理意义把数组看作战场。ans是当前的擂主hp是他的兵力。抵消机制遇到同盟x ans兵力 1遇到敌人x ! ans兵力 -1相当于和一个敌人同归于尽。换人机制当兵力耗尽hp 0时说明之前的擂主已经拼光了当前的x顺势成为新擂主。2. 算法流程 (摩尔投票)初始化 (Init)ans候选众数擂主。hp血量计数器初始为 0。遍历 (Loop)判断换人如果hp 0说明之前的帐算平了或者刚开始。当前数字x登基成为新ans并将hp设为 1。判断阵营如果x ans自己人血量hp。如果x ! ans敌人互砍一刀血量hp--。结果 (Result)题目保证众数存在且所以遍历结束后ans一定是那个众数。 代码回忆清单// 题目LC 169. Majority Element class Solution { public int majorityElement(int[] nums) { int ans 0; // 当前擂主 int hp 0; // 擂主血量 (Count) for (int x : nums) { // 1. 血量归零改朝换代 // 说明之前的候选人已经被消耗殆尽了 if (hp 0) { ans x; // 新王登基 hp 1; // 初始血量 } // 2. 只有血量 0 才会走到这里 else { // 同门加血异类扣血 (一换一) hp (x ans) ? 1 : -1; } } return ans; } }⚡ 快速复习 CheckList (易错点)[ ]为什么这个算法管用它的数学本质是如果把众数记为 1其他数记为 -1。因为众数数量 所以整个数组所有元素加起来的总和一定 。不管抵消顺序如何最后剩下的只能是众数。[ ]如果众数不一定存在呢本题保证存在。如果不保证需要在得到ans后再遍历一次数组统计ans的真实出现次数确认它是否真的 。[ ]hp 0的逻辑放在哪里一定要放在循环的最开始或者每次hp变化后检查。如果是else if (hp 0)可能会漏掉处理逻辑最好写成单独的if或者像您代码中那样结构清晰的if-else。️ 数字演练nums [2, 2, 1, 1, 1, 2, 2](众数是 2)Init:ans0, hp0.x2:hp是0。换人-ans2, hp1。x2:22。加血-hp2.x1:1!2。扣血-hp1.x1:1!2。扣血-hp0. (此时 2 被两个 1 拼光了)x1:hp是0。换人-ans1, hp1. (1 暂时称王)x2:2!1。扣血-hp0. (1 被新来的 2 拼光了)x2:hp是0。换人-ans2, hp1.结束: 返回2。
