目录一、169. 多数元素摩尔投票法O (n) 时间 O (1) 空间题目描述核心思路Java 完整代码复杂度分析二、75. 颜色分类三指针原地排序题目描述核心思路Java 完整代码复杂度分析三、总结面试必背大家好今天分享两道经典算法题 ——169. 多数元素简单和75. 颜色分类中等都是面试高频考点我会用最优解法 完整 Java 可运行代码实现新手也能直接看懂、直接运行。一、169. 多数元素摩尔投票法O (n) 时间 O (1) 空间题目描述给定一个大小为n的数组找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n/2⌋的元素题目保证一定存在。核心思路利用摩尔投票法维护一个候选值candidate和计数器count相同数字计数 1不同数字计数 - 1计数器归零时更换候选值最终剩下的候选值就是多数元素因为它永远无法被完全抵消Java 完整代码java运行public class MajorityElement { // 核心方法摩尔投票法 public int majorityElement(int[] nums) { int candidate 0; int count 0; for (int num : nums) { // 计数器归零更换候选人 if (count 0) { candidate num; } // 相同1不同-1 count (num candidate) ? 1 : -1; } return candidate; } // 测试主函数 public static void main(String[] args) { MajorityElement solution new MajorityElement(); int[] nums {2, 2, 1, 1, 1, 2, 2}; System.out.println(多数元素 solution.majorityElement(nums)); // 输出2 } }复杂度分析时间复杂度O (n)仅遍历一次数组空间复杂度O (1)无额外空间开销二、75. 颜色分类三指针原地排序题目描述给定一个包含红色、白色、蓝色共n个元素的数组原地对它们进行排序使得相同颜色的元素相邻并按照 0红、1白、2蓝顺序排列。不能使用库函数排序。核心思路三指针法荷兰国旗问题p00 的右边界左边全是 0p22 的左边界右边全是 2curr当前遍历指针遇到 0 放左边遇到 2 放右边遇到 1 跳过Java 完整代码java运行public class SortColors { public void sortColors(int[] nums) { int p0 0; int curr 0; int p2 nums.length - 1; while (curr p2) { if (nums[curr] 0) { // 交换 0 到左区 swap(nums, curr, p0); p0; curr; } else if (nums[curr] 2) { // 交换 2 到右区 swap(nums, curr, p2); p2--; } else { // 1 留在中间直接跳过 curr; } } } // 数组交换工具方法 private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } // 测试主函数 public static void main(String[] main) { SortColors solution new SortColors(); int[] nums {2, 0, 2, 1, 1, 0}; solution.sortColors(nums); System.out.print(排序结果); for (int num : nums) { System.out.print(num ); } // 输出0 0 1 1 2 2 } }复杂度分析时间复杂度O (n)一次遍历完成排序空间复杂度O (1)原地排序无额外空间三、总结面试必背多数元素用摩尔投票法空间最优面试高频送分题颜色分类用三指针属于荷兰国旗问题原地排序经典题两道题都做到了O (n) 时间 O (1) 空间是最优解