在 C++ 中以线性时间找到长度为 3 的递增子序列

在本文中，您将学习如何在 C++ 中以线性时间查找大小为 3 的有序子序列。

问题描述如下：

给定一个数字数组，您的任务是查找一个包含三个元素的子序列，其中所有三个数字都应按排序顺序排列。子序列的条件是元素的索引应递增。元素的条件应按递增顺序排列。如果数组名为 nums，则子序列在索引 i, j, k 处有三个数字。

nums[i] < nums[j] < nums[k]

i < j < k

上述问题的解决方案（方法 1）

输出

程序中存在的变量有

• "n" 表示数组的长度或数组中存在的元素数量。
• "nums" 是存储所有元素的向量。
• "small" 变量用于跟踪数组中的最小元素。
• "large" 变量用于跟踪数组中的第二小元素。
• "index_small" 用于存储 small 的索引。
• "result" 是存储子序列的向量。

程序中使用的函数有

• findSortedSubsequnece：此函数接受向量 nums 并返回结果。
• main：此函数用于启动程序。

说明

• 在此示例中，第一行用于用户输入并将其存储在向量中。
• 在函数中，它检查输入向量的长度是否大于或等于 3，如果小于 3，则返回一个空向量，因为我们无法形成包含三个元素的子序列。
• 之后，我们将 small 和 large 初始化为最大可能的整数值，并将 small_index 初始化为 -1。
• 如果当前元素小于或等于 small，它将 small 更新为当前元素，并将 index_small 设置为当前索引。
• 如果当前元素大于 small 但小于或等于 large，它将 large 更新为当前元素。
• 如果当前元素大于 small 和 large，则表示找到了大小为 3 的有序子序列。函数创建一个包含 small、large 和当前元素的 result 向量，并返回此向量。

上述问题的解决方案（方法 2）

输出

函数中存在的变量有

• 在此示例中，"n" 用于指示向量中存在的元素数量。
• "nums" 是输入向量的名称。
• "max" 存储数组右侧最大元素的索引。
• "min" 存储数组左侧最小元素的索引。
• "i" 变量用于迭代。
• "left_array" 向量将存储直到该特定索引的最小元素的索引。
• "right_array" 存储 nums 中每个元素右侧较大元素的索引。

上述程序中使用的函数有

• findSortedSubsequence：此函数不返回任何内容，但接受输入向量。
• 在此函数中，仅使用两个不同的向量来获取结果。
• main：它是启动执行的主函数。

说明

• 它构造 left_array，存储左侧较小元素的索引。
• 它构造 right_array，存储右侧较大元素的索引。
• 该函数遍历数组并检查左右元素。
• 如果找到，它会打印三元组并退出。
• 如果未找到三元组，它会打印 "未找到此类三元组"。
• 处理输入数组元素少于 3 个的情况，并提供适当的消息。