微软intern面经，求答案

上周面微软，死的好惨。除了问问background以外，其实就一道题。

题目

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

，merge的方法又需要额外的空间，其它的类似于排序的方法复杂度又要大于或等有O（n^2），求高手指点

从左往右，遇到一个正数就往前面冒泡直到遇到另一个正数吗？

回复 2# Imbalism

这是O（n^2）吧

回复 1# smzfeng
他不会是想用递归，然后不用数组就认为空间复杂度低吧
否则你在数组中寻找未排序的负数，这个操作就是n^2

回复 4# tiexuelangren

应该不会吧……毕竟是微软的面试，应该不会有这样的玩笑……

回复 5# smzfeng
如果不借助额外的空间，从n个元素中寻找第一个负数，从n-1个中寻找第一个负数.....这个操作的复杂度没法降低。最小就是n^2

哈哈, 不是吧, 微软面试会有这么难的题??是OnSite??
这题刻是当年在mitbbs上几个月没人给出合适解答, 你撞大运了

这不是版大发的100道题的原题吗？可以去编程区找到！
版大V587！

这样可以嘛
从头开始，过一遍这个数组，每当读到一个负数， 就把这个数移到数组末尾
读n个数就停止。数据结构用链表会比较好

回复 7# wwwyhx


    求版大给解答