一个未排序整数数组,有正负数,重新排列使负数排在正数前面,并且要求不改变原来的 相对顺序 比如: input: 1,7,-5,9,-12,15 ans: -5,-12,1,7,9,15 要求时间复杂度O(N),空间O(1) 。(此题一直没看到令我满意的答案,一般达不到题目所要求的:时间复杂度O(N),空间O(1))
找到答案了,来完善一下。 引入两个指针即可,思路如下:
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;
欢迎来到随意问技术百科, 这是一个面向专业开发者的IT问答网站,提供途径助开发者查找IT技术方案,解决程序bug和网站运维难题等。 温馨提示:本网站禁止用户发布与IT技术无关的、粗浅的、毫无意义的或者违法国家法规的等不合理内容,谢谢支持。