数组是算法中最基础也最重要的数据结构之一。很多看似简单的题目背后都藏着从能跑通到跑得快的思维跃迁。今天通过三道数组相关的经典题目聊聊如何先写出最容易想到的解法再一步步逼近最优解。题一在有序数组中搜索插入位置问题描述给定一个按升序排列的数组和一个目标值如果目标值存在于数组中返回它的索引如果不存在返回它应该被插入的位置以保证数组仍然有序。要求算法的时间复杂度为对数级别。最容易想到的方法线性扫描看到查找两个字很多人的第一反应是从头到尾遍历一遍int searchInsert(int nums[], int numsSize, int target) { for (int i 0; i numsSize; i) { if (nums[i] target) { return i; } } return numsSize; }这个思路非常直观数组是有序的从左往右找第一个大于或等于目标值的位置就是我们要的答案如果都比目标值小就放在末尾。复杂度分析最坏情况下需要遍历整个数组时间复杂度是O(n)。最优解二分查找题目特意强调了对数级别的时间复杂度这其实是一个强烈的提示数组已经有序为什么不利用这个特性呢有序数组的查找天然适合二分查找。我们维护两个指针left和right每次取中间元素与目标值比较如果中间元素等于目标值直接返回索引如果中间元素大于目标值说明目标值或插入位置在左半部分如果中间元素小于目标值说明目标值或插入位置在右半部分。循环结束时left指针指向的位置就是目标值应该插入的位置。int searchInsert(int nums[], int numsSize, int target) { int left 0; int right numsSize - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }复杂度分析每次查找范围缩小一半时间复杂度为O(log n)空间复杂度O(1)。思维收获线性扫描忽略了数组已有序这个关键条件而二分查找正是利用有序性来减少搜索空间的典范。遇到有序数据先想想能不能用二分。题二大整数加一问题描述给定一个整数数组数组中的每个元素代表大整数的一位数字从左到右是高位到低位。这个大整数没有前导零。要求将这个大整数加一返回结果数组。最容易想到的方法转成数字再运算初学者可能会想把数组拼成一个整数加一后再拆回数组。// 伪代码示意实际不推荐 long long num 0; for (int i 0; i digitsSize; i) { num num * 10 digits[i]; } num num 1; // 再将 num 拆分成数组...这个思路在数学上没错但有一个致命问题当数组很长时整数会溢出。比如数组有 100 位任何内置的整数类型都存不下。题目用数组表示大整数就是为了规避溢出问题。最优解模拟进位既然不能转数字那就模拟我们小学时学的竖式加法。加一只影响末尾从数组最后一位开始如果当前位小于 9直接加一并返回结束如果当前位是 9加一后变成 0并向前一位进 1如果遍历完所有位都是 9比如[9, 9, 9]最后需要在最前面插入一个 1。int* plusOne(int digits[], int digitsSize, int* returnSize) { for (int i digitsSize - 1; i 0; i--) { if (digits[i] 9) { digits[i]; *returnSize digitsSize; return digits; } digits[i] 0; } // 走到这里说明全是9需要扩容 int* result (int*)malloc((digitsSize 1) * sizeof(int)); result[0] 1; for (int i 1; i digitsSize; i) { result[i] 0; } *returnSize digitsSize 1; return result; }复杂度分析最坏情况下遍历一次数组比如999时间复杂度O(n)。这是最优的因为每个元素至少要检查一次。空间复杂度O(1)不考虑扩容时的额外空间。思维收获转数字的思维被日常编程惯坏了遇到大数问题要立刻警觉。模拟手工计算的过程往往是最可靠也最通用的解法。题三合并两个有序数组问题描述给定两个按非递减顺序排列的整数数组将第二个数组合并到第一个数组中使合并后的数组仍然有序。注意第一个数组的初始长度足够容纳两个数组的所有元素其后半部分用 0 占位。最容易想到的方法先合并再排序既然第一个数组后面有空位那直接把第二个数组的元素拷贝过去然后对整个数组排序// 将 nums2 的元素放到 nums1 的尾部 for (int i 0; i n; i) { nums1[m i] nums2[i]; } // 对 nums1 排序调用排序函数 sort(nums1, m n);这个方案写起来最快思路也最直白。复杂度分析排序的时间复杂度通常是O((mn) log(mn))没有利用两个数组已经有序的条件。最优解从后往前的双指针两个数组都是有序的这提示我们可以用归并排序中的合并思想。但这里有个陷阱如果从头开始比较把较小的数放到nums1前面可能会覆盖nums1中尚未比较的元素。换个方向思考既然nums1后面有空位为什么不从尾部开始填充呢指针i指向nums1有效元素的末尾索引m-1指针j指向nums2的末尾索引n-1指针k指向nums1的末尾索引mn-1。每次比较nums1[i]和nums2[j]把较大的那个放到nums1[k]然后相应指针前移。void merge(int nums1[], int nums1Size, int m, int nums2[], int nums2Size, int n) { int i m - 1; // nums1 有效数据末尾 int j n - 1; // nums2 末尾 int k m n - 1; // nums1 末尾 while (i 0 j 0) { if (nums1[i] nums2[j]) { nums1[k--] nums1[i--]; } else { nums1[k--] nums2[j--]; } } // 如果 nums2 还有剩余拷贝到前面 while (j 0) { nums1[k--] nums2[j--]; } // nums1 剩余元素已经在正确位置无需处理 }复杂度分析每个元素只被访问一次时间复杂度O(mn)空间复杂度O(1)。相比排序方案这是一个质的飞跃。思维收获当正向操作会破坏已有数据时不妨考虑逆向思维。从后往前填充巧妙地利用了nums1尾部的空闲空间避免了额外数组的开销。