2161. 根据给定枢轴划分数组

📝

内容提要

给定一个整数数组和一个枢轴，重新排列数组，使得小于枢轴的元素在前，等于枢轴的元素在中间，大于枢轴的元素在后，并保持相对顺序，时间复杂度为O(n)。

🎯

关键要点

• 给定一个整数数组和一个枢轴，重新排列数组。

• 小于枢轴的元素在前，等于枢轴的元素在中间，大于枢轴的元素在后。

• 保持小于和大于枢轴的元素的相对顺序。

• 时间复杂度为O(n)。

• 将元素分为三组：小于枢轴、等于枢轴和大于枢轴。

• 通过遍历数组并将元素添加到各自的组中，保持相对顺序。

• 最后合并三组形成重新排列的数组。

🔎

延伸解读

时间复杂度分析

该算法的时间复杂度为O(n)，意味着它能够在一次遍历中完成数组的重新排列。这种效率在处理大规模数据时尤为重要，尤其是在数组长度达到10万时，能够显著提高性能。

相对顺序的重要性

保持小于和大于枢轴元素的相对顺序是该算法的关键特性。这一特性在某些应用场景中非常重要，例如在排序或分组数据时，可能需要保留原始数据的顺序以便于后续处理。

空间复杂度考虑

虽然该算法在时间上是高效的，但其空间复杂度为O(n)，意味着在处理大数组时需要额外的存储空间。开发者在实现时需考虑内存使用，尤其是在资源受限的环境中。

❓

延伸问答

如何根据给定的枢轴重新排列数组？

将小于枢轴的元素放在前面，等于枢轴的元素放在中间，大于枢轴的元素放在后面，并保持相对顺序。

这个算法的时间复杂度是多少？

时间复杂度为O(n)。

如何保持小于和大于枢轴的元素的相对顺序？

通过遍历数组并将元素添加到各自的组中，保持它们在原数组中的相对顺序。

可以给出一个示例吗？

例如，输入数组为[9,12,5,10,14,3,10]，枢轴为10，输出为[9,5,3,10,10,12,14]。

这个算法适用于多大的数组？

适用于长度在1到10^5之间的数组。

如何实现这个算法？

可以通过将元素分为三组：小于、等于和大于枢轴，然后合并这些组来实现。

🏷️

标签

整数数组 时间复杂度 枢轴 相对顺序 重新排列