软装设计素材网站,武邑县网站建设,wordpress火车头采集发布模块,山西省住房建设厅网站房屋建筑定额序言#xff1a;今天是第五题啦#xff0c;前面四题的解法还清楚吗#xff1f;可以到面试算法题系列150题专栏 进行复习呀。
温故而知新#xff0c;可以为师矣#xff01;加油#xff0c;未来的技术大牛们。 多数元素
给定一个大小为 n 的数组 nums #xff0c;返回其…序言今天是第五题啦前面四题的解法还清楚吗可以到面试算法题系列150题专栏 进行复习呀。
温故而知新可以为师矣加油未来的技术大牛们。 多数元素
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例 1
输入nums [3,2,3]
输出3
示例 2
输入nums [2,2,1,1,1,2,2]
输出2实现思路这个问题是经典的多数投票问题Boy Scout Rule可以使用摩尔投票算法Moores Voting Algorithm来解决。这个算法的核心思想是使用两个变量一个记录当前的候选多数元素另一个记录该元素的票数。遍历数组对于每个元素如果它与当前候选元素相同则增加票数如果不同则减少票数。如果在减少票数后票数变为0则将当前元素作为新的候选多数元素。
实现代码
public int majorityElement(int[] nums) {int candidate nums[0]; // 当前候选多数元素int count 1; // 当前候选元素的票数// 摩尔投票算法的主体for (int i 1; i nums.length; i) {if (count 0) {candidate nums[i]; // 重置候选元素count 1; // 重置票数} else if (nums[i] candidate) {count; // 如果当前元素与候选元素相同增加票数} else {count--; // 如果当前元素与候选元素不同减少票数}}// 根据题目保证不需要验证步骤直接返回候选多数元素return candidate;
}
这个方法的时间复杂度是 O(n)空间复杂度是 O(1)因为它只需要常数级别的额外空间。
小补充如果数组是非空的给定数组不一定存在多数元素呢怎么实现呢
思路上述代码是选出可能为多数元素的候选元素我们只要在这个基础上对其进行判断是否为多数元素即可。
实现代码
public int majorityElement(int[] nums) {int candidate nums[0]; // 当前候选多数元素int count 1; // 当前候选元素的票数for (int i 1; i nums.length; i) {if (nums[i] candidate) {count; // 如果当前元素与候选元素相同增加票数} else {if (count 0) {candidate nums[i]; // 票数归零更新候选元素} else {count--; // 如果当前元素与候选元素不同减少票数}}}// 验证候选元素是否确实是多数元素int result 0;int validCount 0;//记录候选元素的个数for (int num : nums) {if (num candidate) {validCount;}}// 如果候选元素的票数大于数组长度的一半则返回该元素if (validCount nums.length / 2) {return candidate;}// 如果没有找到多数元素则返回0return 0;
} 知识复习int num : nums 是一种被称为“增强型for循环”Enhanced For Loop的语法结构它用于遍历数组或集合中的每个元素。这个语法结构允许你用一种简洁的方式迭代数组或Iterable对象。 int num这定义了一个名为 num 的变量它将用于接收数组或集合中的当前元素。在这个上下文中num 是每次循环中的元素变量名你可以使用任何有效的变量名。 :冒号这个符号用于分隔变量定义和迭代的对象。 nums这是被迭代的对象可以是一个数组或实现了 Iterable 接口的集合。
整个表达式 int num : nums 的意思是“对于数组或集合 nums 中的每个元素用变量 num 引用它”。
下面是一个使用这种语法遍历数组的示例
int[] nums {1, 2, 3, 4, 5};for (int num : nums) {// 打印数组中的每个元素System.out.println(num);}
这段代码将打印
1
2
3
4
5
每个循环迭代中数组 nums 中的当前元素都会被赋值给变量 num然后执行循环体内的代码。这种语法使得遍历数组和集合变得更加简洁和易于阅读。
