数组（数据结构与算法 - 5）
内容提要
本文介绍了常见的数组和栈操作算法，包括去重、移动零、找缺失数字、找只出现一次的数字、Kadane算法、最长公共序列、重新排列数组、找大多数元素、两数之和、旋转数组、二叉搜索树中的第k个最小元素、荷兰国旗问题、股票买卖、查找元素、矩阵置零、二分查找、中缀转后缀、中缀转前缀、后缀转中缀、后缀转前缀、单调栈等。
延伸解读
数组算法中的原地操作与空间权衡
文章中的多个算法强调原地操作，如去重和移动零，这有助于减少额外空间。但原地操作可能改变元素顺序或需要额外变量，实际应用中需根据是否允许修改原数组来选择。例如，去重算法要求数组已排序，否则需先排序，增加时间复杂度。
位运算与数学方法在查找问题中的应用
寻找缺失数字和只出现一次的数字时，文章展示了异或和求和两种方法。异或法能避免整数溢出，且适用于特定场景；求和法则更直观，但可能在大数时溢出。选择时需考虑数据范围和语言特性。
栈在表达式转换与单调栈中的核心作用
文章详细介绍了中缀、前缀、后缀表达式之间的转换，均基于栈实现。同时，单调栈用于解决下一个更大元素等问题。这些例子体现了栈在处理嵌套结构和维护单调性时的优势，是算法中的基础工具。
二分查找的变体与边界处理
文章涵盖了二分查找的多种变体，如查找下界、峰值元素、旋转排序数组等。这些变体需要仔细处理边界条件和循环不变量，例如计算中点时使用low+(high-low)/2防止溢出。理解这些细节对正确实现至关重要。
Q&A
如何从排序数组中原地去重？
可以使用双指针法，遍历数组，将不重复的元素移动到前面，最后返回新数组的长度。
如何将数组中的零移动到末尾？
遍历数组，使用一个指针记录非零元素的位置，将非零元素交换到前面，最后返回修改后的数组。
Kadane算法的主要用途是什么？
Kadane算法用于求解最大子数组和，可以在O(n)时间复杂度内找到数组中和最大的连续子数组。
如何找到数组中只出现一次的数字？
可以使用异或运算，遍历数组，将所有元素进行异或，最后得到的结果即为只出现一次的数字。
如何实现二分查找？
通过设置左右边界，计算中间位置，判断中间值与目标值的关系，逐步缩小查找范围，直到找到目标值或范围为空。
如何在二叉搜索树中找到第k个最小元素？
可以进行中序遍历，将元素按顺序存储到数组中，返回数组中第k-1个元素。
