DEV Community
·
2161. 根据给定枢轴划分数组
💡
原文英文，约800词，阅读约需3分钟。
📝
内容提要
给定一个整数数组和一个枢轴，重新排列数组，使得小于枢轴的元素在前，等于枢轴的元素在中间，大于枢轴的元素在后，并保持相对顺序，时间复杂度为O(n)。
🎯
关键要点
-
给定一个整数数组和一个枢轴，重新排列数组。
-
小于枢轴的元素在前，等于枢轴的元素在中间，大于枢轴的元素在后。
-
保持小于和大于枢轴的元素的相对顺序。
-
时间复杂度为O(n)。
-
将元素分为三组：小于枢轴、等于枢轴和大于枢轴。
-
通过遍历数组并将元素添加到各自的组中，保持相对顺序。
-
最后合并三组形成重新排列的数组。
❓
延伸问答
如何根据给定的枢轴重新排列数组？
将小于枢轴的元素放在前面，等于枢轴的元素放在中间，大于枢轴的元素放在后面，并保持相对顺序。
这个算法的时间复杂度是多少？
时间复杂度为O(n)。
如何保持小于和大于枢轴的元素的相对顺序？
通过遍历数组并将元素添加到各自的组中，保持它们在原数组中的相对顺序。
可以给出一个示例吗？
例如，输入数组为[9,12,5,10,14,3,10]，枢轴为10，输出为[9,5,3,10,10,12,14]。
这个算法适用于多大的数组？
适用于长度在1到10^5之间的数组。
如何实现这个算法？
可以通过将元素分为三组：小于、等于和大于枢轴，然后合并这些组来实现。
➡️
