您好,匿名用户
随意问技术百科期待您的加入

一个要求时间复杂度O(N),空间O(1)的排序问题

0 投票

一个未排序整数数组,有正负数,重新排列使负数排在正数前面,并且要求不改变原来的 相对顺序 比如: input: 1,7,-5,9,-12,15 ans: -5,-12,1,7,9,15 要求时间复杂度O(N),空间O(1) 。(此题一直没看到令我满意的答案,一般达不到题目所要求的:时间复杂度O(N),空间O(1))

用户头像 提问 2012年 12月1日 @ Morgana 上等兵 (251 威望)
分享到:

1个回答

0 投票
 
最佳答案

找到答案了,来完善一下。
引入两个指针即可,思路如下:

input[] = {1,7,-5,9,-12,15};
pts=&input[i]; pti=&input[i];
n=1;
for(i=0;i<sizeof(input)-2;i++) {
   pts++;
   if (*(pts-1)<0) {
      (pts-2)->next = pts;
      (pts-1)->next = pti;
   }

   if(n && 0>*pti)
      pti++;
   else
      n=0;
}
if (0>input[sizeof(input)-1])
   input[sizeof(input)-1]->next=pti;
用户头像 回复 2012年 12月1日 @ Nidalee 上等兵 (346 威望)
选中 2012年 12月1日 @Morgana
提一个问题:

相关问题

0 投票
1 回复 34 阅读
用户头像 提问 2013年 10月27日 @ Malphite 上等兵 (306 威望)
0 投票
1 回复 50 阅读
用户头像 提问 2012年 12月1日 @ Galio 上等兵 (289 威望)
0 投票
1 回复 53 阅读
用户头像 提问 2012年 12月1日 @ hacker 上等兵 (362 威望)
+1 投票
0 回复 25 阅读
0 投票
1 回复 31 阅读
用户头像 提问 2013年 11月7日 @ Sion 上等兵 (319 威望)

欢迎来到随意问技术百科, 这是一个面向专业开发者的IT问答网站,提供途径助开发者查找IT技术方案,解决程序bug和网站运维难题等。
温馨提示:本网站禁止用户发布与IT技术无关的、粗浅的、毫无意义的或者违法国家法规的等不合理内容,谢谢支持。

欢迎访问随意问技术百科,为了给您提供更好的服务,请及时反馈您的意见。
...