关于stable_partition的问题
高洛峰
高洛峰 2016-11-01 10:00:06
0
1
818

题目:假设一整型数组存在若干正数和负数,现在通过某种算法使得该数组的所有负数在正数的左边,且保证负数和正数间元素相对位置不变。时空复杂度要求分别为:o(n)和o(1)。

大概就是要求stable_partition的实现,然而stl中stable_partition实现利用了额外的空间,不符合题目要求呢。

正常会有两种实现方法:

(一)用一个游标,从前往后遍历,第一次遇到负数则继续,遇到正数则记录并接着走,再遇到负数则与刚记录的正数互换,并将记录后移一位,这样遍历完成的时候移位也完成了。

(二)用两个游标,一个位于数组头,往后遍历,一个位于数组尾,往前遍历。前面的遇到负数后面的遇到正数组则继续;前面的遇到正数后面的遇到负数则互换,直到后面游标小于前面游标算完成。

但是都不满足稳定性的要求,毕竟快排是不稳定的排序。那这题应该怎么做呢。再花o(n)时间,把后半部分不稳定的地方给找到再rotate??感觉好蛋疼。


高洛峰
高洛峰

拥有18年软件开发和IT教学经验。曾任多家上市公司技术总监、架构师、项目经理、高级软件工程师等职务。 网络人气名人讲师,...

membalas semua (1)
三叔

假设负数是o,正数是x。
从前往后遍历,每次找到xx..xoo..o的子串,进行循环左移变为oo..oxx..x;
下一次从上一次的x开始计算新的xx..xoo..o子串模式来转换。
每个字符最多被操作两次,因此复杂度是O(N)。
剩下的就是如果将xx..xoo..o在O(L)的复杂度内完成oo.oxx..x的变化。假设模式串为x1x2x3x4o1o2o3, 范围内两次倒置,第一次将两个子串分别反转,得到x4x3x2x1o3o2o1,第二次整体倒置得到o1o2o3x1x2x3x4。完成。一共是2*L次。
综上,时间复杂度O(N),每个元素最多移动了4次.空间复杂度O(1)

    Muat turun terkini
    Lagi>
    kesan web
    Kod sumber laman web
    Bahan laman web
    Templat hujung hadapan
    Tentang kita Penafian Sitemap
    Laman web PHP Cina:Latihan PHP dalam talian kebajikan awam,Bantu pelajar PHP berkembang dengan cepat!