DEV Community
·
数组（数据结构与算法 - 5）
内容提要
本文介绍了常见的数组和栈操作算法，包括去重、移动零、找缺失数字、找只出现一次的数字、Kadane算法、最长公共序列、重新排列数组、找大多数元素、两数之和、旋转数组、二叉搜索树中的第k个最小元素、荷兰国旗问题、股票买卖、查找元素、矩阵置零、二分查找、中缀转后缀、中缀转前缀、后缀转中缀、后缀转前缀、单调栈等。
关键要点
-
从排序数组中原地去重的算法
-
将数组中的零移动到末尾的算法
-
寻找缺失数字的算法
-
找出只出现一次的数字的算法
-
Kadane算法用于求最大子数组和
-
寻找最长公共序列的算法
-
根据符号重新排列数组的算法
-
找出大多数元素的算法
-
两数之和的算法
-
寻找缺失和重复数字的算法
-
旋转数组的算法
-
在二叉搜索树中找到第k个最小元素的算法
-
荷兰国旗问题的解决方案
-
股票买卖的最大利润算法
-
在矩阵中查找元素的算法
-
将矩阵置零的算法
-
二分查找的实现
-
寻找数字的下界的算法
-
寻找峰值元素的算法
-
在旋转排序数组中查找元素的算法
-
计算两个不同大小的已排序数组的中位数的算法
-
计算前缀和的算法
-
滑动窗口最大子数组和的算法
-
栈的基本操作和使用
-
验证括号有效性的算法
-
单调栈的实现
-
中缀表达式转后缀表达式的算法
-
中缀表达式转前缀表达式的算法
-
后缀表达式转中缀表达式的算法
-
后缀表达式转前缀表达式的算法
-
前缀表达式转后缀表达式的算法
-
后缀表达式转前缀表达式的算法
-
单调栈的应用
延伸问答
如何从排序数组中原地去重？
可以使用双指针法，遍历数组，将不重复的元素移动到前面，最后返回新数组的长度。
如何将数组中的零移动到末尾？
遍历数组，使用一个指针记录非零元素的位置，将非零元素交换到前面，最后返回修改后的数组。
Kadane算法的主要用途是什么？
Kadane算法用于求解最大子数组和，可以在O(n)时间复杂度内找到数组中和最大的连续子数组。
如何找到数组中只出现一次的数字？
可以使用异或运算，遍历数组，将所有元素进行异或，最后得到的结果即为只出现一次的数字。
如何实现二分查找？
通过设置左右边界，计算中间位置，判断中间值与目标值的关系，逐步缩小查找范围，直到找到目标值或范围为空。
如何在二叉搜索树中找到第k个最小元素？
可以进行中序遍历，将元素按顺序存储到数组中，返回数组中第k-1个元素。
