前言今天复盘两道面试高频的数组题一道是利用摩尔投票算法的经典题「多数元素」另一道是荷兰国旗问题的典型应用「颜色分类」。这两道题分别代表了 “特殊条件下的最优解” 和 “原地排序的双指针技巧”是数组处理中非常实用的算法模板。一、169. 多数元素简单题目描述给定一个大小为n的数组找到其中的多数元素。多数元素是指在数组中出现次数大于⌊n/2⌋的元素。 你可以假设数组是非空的并且给定的数组总是存在多数元素。核心思路摩尔投票算法摩尔投票算法的核心思想是 **“正负抵消”**因为多数元素的出现次数超过一半所以它在和其他元素两两抵消后最终一定会剩下。维护一个候选元素candidate和它的票数count遍历数组若count 0将当前元素设为新的候选若当前元素等于候选count否则count--遍历结束后candidate就是多数元素完整代码Javajava运行class Solution { 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)仅使用常数额外空间拓展思考摩尔投票算法还可以拓展到 “找出数组中出现次数大于n/3的元素”最多有两个候选元素需要两轮遍历第一轮投票找出候选第二轮验证是否满足条件。二、75. 颜色分类中等题目描述给定一个包含红色、白色和蓝色一共n个元素的数组原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。 我们使用整数0、1和2分别表示红色、白色和蓝色。注意不能使用库函数来排序必须原地解决。核心思路双指针荷兰国旗问题这道题的最优解法是三指针原地交换核心思想是定义p0指向0元素的右边界p2指向2元素的左边界curr指向当前遍历元素遍历数组若nums[curr] 0将其与nums[p0]交换p0、curr若nums[curr] 2将其与nums[p2]交换p2--此时curr不前进因为交换过来的元素还需要判断若nums[curr] 1直接curr完整代码Javajava运行class Solution { public void sortColors(int[] nums) { int p0 0, curr 0; int p2 nums.length - 1; while (curr p2) { if (nums[curr] 0) { swap(nums, curr, p0); p0; curr; } else if (nums[curr] 2) { swap(nums, curr, p2); p2--; } else { curr; } } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } }复杂度分析时间复杂度O (n)仅需一次遍历数组空间复杂度O (1)原地交换未使用额外空间拓展思考荷兰国旗问题可以拓展到更多颜色的排序场景核心思想都是通过指针将元素分区一次遍历完成排序避免了多次遍历或额外空间的开销。两道题对比总结表格题目核心思想时间复杂度空间复杂度关键考点多数元素摩尔投票算法正负抵消O(n)O(1)多数元素的定义、投票过程颜色分类三指针原地分区荷兰国旗问题O(n)O(1)双指针技巧、原地交换