在算法学习中拿到题目后先想出一个能跑通的解法再逐步优化到最优解是非常有效的训练方式。本文通过三道经典的数组问题分别展示最容易想到的直观解法与更优的巧妙解法希望能帮助你建立先暴力、后优化的解题思维。题一生成杨辉三角的前 n 行问题描述给定一个非负整数numRows生成杨辉三角的前numRows行。在杨辉三角中每个数是它左上方和右上方数的和。直观思路按定义模拟杨辉三角的规律非常清晰每行的第一个数和最后一个数都是 1中间的每个数等于上一行中相邻两个数之和因此最直观的想法就是从第 1 行开始逐行生成。生成第i行时只需要查看第i-1行的数据即可。复杂度分析由于需要生成全部numRows行的所有元素时间复杂度为 O(numRows²) 。结果本身就需要 O(numRows²) 的空间来存储因此这个复杂度是合理的模拟本身就是最优解法。如果题目只要求返回某一行我们可以只用一维数组滚动更新将空间优化到 O(numRows) 。但本题需要返回所有行因此直接模拟即可。代码实现#include stdio.h #define MAX_ROWS 30 #define MAX_COLS 30 int main() { int numRows 5; int triangle[MAX_ROWS][MAX_COLS] {0}; for (int i 0; i numRows; i) { triangle[i][0] 1; // 每行第一个数为 1 triangle[i][i] 1; // 每行最后一个数为 1 // 中间元素等于左上方和上方元素之和 for (int j 1; j i; j) { triangle[i][j] triangle[i-1][j-1] triangle[i-1][j]; } } // 输出结果 for (int i 0; i numRows; i) { for (int j 0; j i; j) { printf(%d , triangle[i][j]); } printf(\n); } return 0; }题二找出只出现一次的数字问题描述给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。要求算法具有线性时间复杂度且只使用常量额外空间。最优解异或运算这道题的最优解法非常巧妙需要借助位运算中的异或^。异或运算有三个关键性质自反性a ^ a 0相同的数异或结果为 0恒等性a ^ 0 a任何数与 0 异或结果不变交换律与结合律运算顺序不影响最终结果基于以上性质将数组中所有元素依次异或出现两次的两个相同数字会相互抵消为 0最后剩下的结果就是那个只出现一次的数字复杂度分析只需要遍历数组一次时间复杂度 O(n) 仅使用一个变量存储异或结果空间复杂度 O(1) 。代码实现#include stdio.h int findSingle(int nums[], int numsSize) { int result 0; for (int i 0; i numsSize; i) { result result ^ nums[i]; // 依次异或所有元素 } return result; } int main() { int nums[] {4, 1, 2, 1, 2}; int numsSize 5; printf(只出现一次的数字是: %d\n, findSingle(nums, numsSize)); return 0; }题三找出数组中的多数元素问题描述给定一个大小为n的数组返回其中的多数元素。多数元素是指在数组中出现次数严格大于⌊n/2⌋的元素。可以假设数组非空且总是存在多数元素。直观思路统计每个元素出现次数和题二类似第一反应通常是用辅助数组或哈希表统计每个元素的出现频率遍历统计结果找到出现次数超过n/2的元素复杂度分析时间复杂度 O(n) 空间复杂度 O(n) 。思路简单直接但空间开销较大。最优解摩尔投票法Boyer-Moore 投票算法摩尔投票法的核心思想非常形象多数元素的支持者超过一半即使和其他所有元素“一对一抵消”最终也一定能剩下。具体做法设定一个candidate候选人和一个count票数计数器遍历数组若count 0说明当前候选人已被完全抵消选择当前元素作为新的候选人票数置为 1若当前元素等于候选人票数 1若当前元素不等于候选人票数 -1相当于一次“抵消”遍历结束后candidate就是多数元素为什么正确因为多数元素出现次数超过n/2即使它和其他所有不同的元素一一配对抵消最终至少还会剩余一票。复杂度分析只遍历数组一次时间复杂度 O(n) 只使用两个变量空间复杂度 O(1) 。代码实现#include stdio.h int majorityElement(int nums[], int numsSize) { int candidate nums[0]; int count 1; for (int i 1; i numsSize; i) { if (count 0) { // 候选人被抵消完更换候选人 candidate nums[i]; count 1; } else if (nums[i] candidate) { count; // 遇到支持者票数加 1 } else { count--; // 遇到反对者票数减 1抵消 } } return candidate; } int main() { int nums[] {2, 2, 1, 1, 1, 2, 2}; int numsSize 7; printf(多数元素是: %d\n, majorityElement(nums, numsSize)); return 0; }
