Interview Questions 3: Sort negative and positive numbers

问题描述: 

给你一个整数数组, 里面有整数负数, 要求重新安排每个元素的位置, 使得所有负数在整数的前面, 并且保证原先正负数的相对位置不变.

比如
1,71,-5,9,-11,15
要求变成
-5,-11,1,71,9,15

解决办法:

方法一, O(N)时间, O(N)空间: 利用额外的数组, 第一个pass拷贝原数组到额外数组, 第二个pass把额外数组的所有负数按照原先顺序存回原来数组里面,第三个pass同样方法把正数append到原来数组里面, 参考代码如下:

void reorder(std::vector<int> &nums) {
    int len = nums.size();
    std::vector<int> nums_copy = nums;
    int cnt = 0;
    for(int i = 0; i < len; ++i) {
        if(nums_copy[i] < 0) nums[cnt++] = nums_copy[i];
    }
    for(int i = 0; i < len; ++i) {
        if(nums_copy[i] > 0) nums[cnt++] = nums_copy[i];
    }
    return ;
}

方法二, O(N^2)时间, O(1)空间: 线性扫描原数组, 如果遇到正数, 用一个变量记录该正数, 把该正数后面的所有元素往前shift一个位置, 同时把该正数appled到数组最后. 代码略.

方法三, O(NlogN)时间, O(logN)空间: 利用分治算法, 每次对数组的两边进行重新排序, 同时返回两个half部分的正负数分界点. 然后可以在线性时间内将left part中的正数部分和right part中的负数部分交换, 那么整体就符合要求了. 参考代码如下:

int reorder3(std::vector<int> &nums, int p, int r) {
    if(p > r) {
        return -1;
    }
    if(p == r) {
        if(nums[p] < 0)
            return -1;
        else
            return p;
    }
    if(r - p == 1) {
        if(nums[r] < 0 && nums[p] > 0) {
            std::swap(nums[p], nums[r]);
            return r;
        }
        if(nums[r] > 0 && nums[p] < 0) {
            return r;
        }
        if(nums[r] < 0 && nums[p] < 0) {
            return -1;
        }
        return p;
    }
    // at least there are three elements
    int q = p + (r - p) / 2;
    int left  = reorder3(nums, p, q - 1);
    int right = reorder3(nums, q, r);

    if(-1 == left) return right;
    if(-1 == right) {
        flip(nums, left, q, r); // flip reorders the cross parts in linear time
        return r + 1 - (q - left);
    }
    flip(nums, left, q, right - 1);
    return right - (q - left);
}

方法四, O(N)时间, O(1)空间, 但是打乱相对顺序: 利用快速排序的一次partition就可以搞定. 但是因为快排不稳定, 所以这种方法不能保证相对顺序不变.

后话: 传说有论文发表可以在O(N)时间, O(1)空间搞定同时保证相对顺序不变, 没去研究过. 另外因为题目要求是数组, 如果可以用链表的话, 那也是可以做到O(N)时间, O(1)空间的, 当然了这样就基本上没什么难度了.

(全文完,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on September 11, 2013