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

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

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

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

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

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

评论(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
}
}