考虑 n 张标记为红色或蓝色的卡片
i=1;
j=n;
while(i<n)
{
if(a[i]==RED)
i++;
if(a[j]==BLUE)
j--;
swap(a[i],a[j]);
}
如何使这个就地算法稳定 我可以获得一个 O(n^2) 的问题解决方案 谁能提出一个 O(n) 的解决方案?
最佳答案
如果允许我们使用额外的内存,只需进行 2 遍扫描:
第一关:
count = 0
foreach a[i] == RED
b[count ++] = a[i]
i ++
第二遍:
foreach a[i] == BLUE
b[count ++] = a[i]
i ++
最后复制a = b
总的来说,时间复杂度为 O(3n) = O(n)
。
关于algorithm - 如何将以下不稳定的排序算法转换为稳定的?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25609470/