问
排序布尔值,O(N)时间,O(1)空间
歪友46300606 发布于 2023-02-13 16:43对于家庭作业,我被要求使用使用O(1)空间和O(N)时间复杂度的方法对bool数组进行排序.可以提供任何提示吗？我正在考虑快速排序算法的枢轴方法.-谢谢!
2 个回答
-
如果你有一个布尔数组,你可以简单地计算真(或假)值.让我们假设这个结果为k.然后将数组的前k个元素设置为true,其余为false.
该算法遍历数组两次(因此它具有O(N)时间复杂度),并且仅使用一个计数器,因此所需的空间为O(1).
2023-02-13 16:46 回答
我不是咸鱼仔 -
保持正面和背面的索引.
检查当前的前面索引,如果它的前面索引是假的增量
如果它与后退索引真正交换并减少后退索引
继续步骤2和3,直到前后指数彼此相等
2023-02-13 16:46 回答
yjlz2012
撰写答案
今天，你开发时遇到什么问题呢？
立即提问
京公网安备 11010802041100号