算法-一个未排序整数数组,有正负数,重新排列使负数排在正数前面,并且要求不改变原来的正负数之间相对顺序

Web程序数据库 Web程序数据库 主题:1214 回复:2505

算法-一个未排序整数数组,有正负数,重新排列使负数排在正数前面,并且要求不改变原来的正负数之间相对顺序

灵芸 发布于 2016-12-05 字数 331 浏览 1306 回复 4

一个未排序整数数组,有正负数,重新排列使负数排在正数前面,并且要求不改变原来的正负数之间相对顺序。
比如: input: 1,7,-5,9,-12,15 ,ans: -5,-12,1,7,9,15 。且要求时间复杂度O(N),空间O(1) 。
这是一道面试题,未找到满意的答案,一般达不到题目所要求的:时间复杂度O(N),空间O(1),且保证原来正负数之间的相对位置不变。求解答。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(4

夜无邪 2017-08-27 4 楼

不知道这样满不满足要求:

/**

  • @author Administrator
  • 具体原理:
  • 以栈的形势将负数存在最左边
    /
    import java.util.
    ;
    public class Test
    {
    public static void main(String args[])
    {
    int[]x={1,7,-5,-12,-13,99,-6,31,15};
    int p=0;
    for(int i=x.length-1;i>p;)
    {
    if(x[i]<0)
    {
    int j=i;
    while(j!=0)
    {
    int t=x[j];
    x[j]=x[j-1];
    x[j-1]=t;//交换
    j--;
    }
    p++;
    }
    else i--;
    }
    System.out.println(Arrays.toString(x));
    }
    }
灵芸 2017-08-14 3 楼

首先我从 C++ 语言的角度来考虑这个问题,如果原始数据是放在链表里面的,这个问题应该很好解答。

我假设原始数据是放在数组里面的,因此有了下面的算法,我把它称之为沉积算法,它的原理就是大于零的数往数组后端 “沉”,小于零的数“浮”在前面
PS:我对O(N),O(1)的概念理解不是很清楚,所以算法可能不符合要求吧,请多赐教

#include <iostream>

using namespace std;

int input[] = {1,7,-5,9,-12,15};

template<typename T> void sort_deposit(T* in, size_t len) { int deposit_count = 0; T temp; for(int i = 0; i < len; ++i) { if(in[i] > 0) { ++deposit_count; } else { int count = deposit_count; int base_index = i - count; temp = in[i]; do { in[base_index + count] = in[base_index + count - 1]; } while(--count); in[base_index] = temp; } } }

int main(int argc, char* argv[]) { sort_deposit(input, sizeof(input)/sizeof(int)); for(int i = 0; i < sizeof(input)/sizeof(int); ++i) { cout << input[i] << "t"; } cout << endl; return 0; }

我把数据类型推广到T,在sort_deposit函数里面,只有一个temp是T,所以实际上多用的空间就是一个T的空间,这算满足O(1)吗?
算法缺点是要进行很多次移动,如果T是一个拷贝比较花时间的类型,那么显然算法效率不高,但是主循环只循环数组的长度次,算是O(N)吧?

浮生未歇 2017-03-25 2 楼

算法:
step1:定义int型变量start和end,分别指示数组开始和结束。
step2:while(start<end) step3;step4;step5;
step3: while(arr[start]<0)start++;
step4: while(arr[end]>0)end--;
step5: arr[end]<-->arr[start];

个人意见,仅供参考。

泛泛之交 2017-01-10 1 楼

请参考C++ STL中stable_partition函数的实现。下面是VC10中的一段代码:

template<class _BidIt, class _Pr>
inline _BidIt stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred)
{ // partition preserving order of equivalents, using _Pred
return _First == _Last ? _First
: _Stable_partition(_First, _Last, _Pred, _Dist_type(_First), _Val_type(_First);
}

template<class _BidIt,
class _Pr,
class _Diff,
class _Ty> inline
_BidIt _Stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
_Diff _Count, _Temp_iterator<_Ty>& _Tempbuf)
{ // partition preserving order of equivalents, using _Pred
if (_Count == 0)
return (_First);
else if (_Count == 1)
return (_Pred(_First) ? _Last : _First);
else if (_Count <= _Tempbuf._Maxlen())
{ // temp buffer big enough, copy right partition out and back
_BidIt _Next = _First;
for (_Tempbuf._Init(); _First != _Last; ++_First)
if (_Pred(
_First))
_Next++ = _Move(_First);
else
_Tempbuf++ = _Move(_First);

    _Move(_Tempbuf._First(), _Tempbuf._Last(), _Next);  // copy back
    return (_Next);
    }
else
    {   // temp buffer not big enough, divide and conquer
    _BidIt _Mid = _First;
    _STD advance(_Mid, _Count / 2);

    _BidIt _Left = _Stable_partition(_First, _Mid, _Pred,
        _Count / 2, _Tempbuf);  // form L1R1 in left half
    _BidIt _Right = _Stable_partition(_Mid, _Last, _Pred,
        _Count - _Count / 2, _Tempbuf); // form L2R2 in right half

    _Diff _Count1 = 0;
    _Distance(_Left, _Mid, _Count1);
    _Diff _Count2 = 0;
    _Distance(_Mid, _Right, _Count2);

    return (_Buffered_rotate(_Left, _Mid, _Right,
        _Count1, _Count2, _Tempbuf));   // rotate L1R1L2R2 to L1L2R1R2
    }
}