算法实战笔记：LeetCode 169 多数元素 75 颜色分类

目录

一、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（蓝）顺序排列。不能使用库函数排序。

核心思路

三指针法（荷兰国旗问题）：

• p0：0 的右边界，左边全是 0
• p2：2 的左边界，右边全是 2
• curr：当前遍历指针
• 遇到 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)，原地排序，无额外空间

三、总结（面试必背）

1. 多数元素：用摩尔投票法，空间最优，面试高频送分题
2. 颜色分类：用三指针，属于荷兰国旗问题，原地排序经典题
3. 两道题都做到了O (n) 时间 + O (1) 空间，是最优解