素材牛VIP会员
给定一个2n长的数组将奇数放在偶数前面
 雪***儿  分类:Python  人气:1933  回帖:17  发布于6年前 收藏

给定一个2n长数组,其中n个奇数和n个偶数,对数组进行排序将奇数放在前半部分,偶数放在后半部分。要求:

  1. 不改变原来的奇偶各自的相对顺序

  2. 只申请常数的空间

  3. 时间复杂度为O(n)

举例:给出1 2 3 4 5 6
排序后为 1 3 5 2 4 6

PS:请一定仔细阅读3个条件,去掉其中任意一个都变得简单,并且网上我搜到的答案都是缺少其中某个条件的。因此我怀疑这题是否有解。


看了大家的回答,基本可以分为2种情况:

  1. 用链表可以轻易解决这道题,当然如果把数组转成链表因为需要申请2n长度的next数组,所以认为还是申请额外空间了

  2. 只管输出,如果只要求输出结果那遍历2遍就行了,但这样题目变得太过简单

因为这是一道面试题,我想可以从上面2方面和面试官沟通,我只是凭记忆写下这题,其中也许有自己的一些思维定势(比如没有强调一定是数组,或者没有强调必须要求数组排序只要求输出)。看了大家的讨论还是很有启发的。


找到了国外的链接,看了一圈讨论大部分认为没有O(n)时间O(1)空间的解法
https://www.careercup.com/question?id=5201559730257920


另外说下我自己对这题的一个思考,可以观察到,假如一个数组是符合最终条件的,那么发现当且仅当只交换相邻的两个奇偶数是不会破坏相对顺序的,那么只需给出一个策略找出从最终状态转到题目起始状态的就行了。
另外,不要纠结于奇偶分别的大小问题,比如4 5 3 1 2 6和2 1 3 5 4 6是等价的,只是一个简单的替换,只要将奇数按1 3 5……这样的顺序,偶数按2 4 6……这样的顺序排好就行了。

 标签:算法cc++python

讨论这个帖子(17)垃圾回帖将一律封号处理……

Lv1 新人
编***魔 职业无 6年前#1
var l = [1, 2, 4, 6, 3, 5]
var i=0, item, last = l[l.length-1], count=0;
while(i<l.length){
  count++;
  item = l[i];
  if(item == last){
    break;
  }
  if(item % 2 == 0){
    l.splice(i, 1);
    l.push(item);
  }else{
    i++;
  }
}
console.log(count); //循环执行了多少次
console.log(l); //最后结果

js实现应该是这样的,偶数时释放一个,然后追加到末尾,当处理到初始数组最后一个时停止。 参考了前面moling3650的代码。。

Lv3 码奴
懒***材 职业无 6年前#2

很简单的
用计数排序
假定你的数字范围在0到65535范围之内,定义一个数组count[65536](这个空间是常量,和n无关,所以是O(1) ),初值全部为0。
那么假设有下面这些数字:
100
200
300
119
0
6
...
那么对于每个这个数字,都做在count中记录一下:
100 => count[100]++
200 => count[200]++
300 => count[300]++
119 => count[119]++
0 => count[0]++
6 => count[6]++
...
也就是说:
首先,遍历一遍所有这些数字就可得到0~65535每个数字的个数(在count数组中)
然后,再顺序遍历count数组,count[n] = m,则输出m个n,(比如说有count[3] = 2, 那么说明有2个数字3),依次输出,最后可得结果。
在输出时:
先输出奇数count[1],count[3]...
再输出偶数count[0],count[2]...
复杂度分析:
第一次遍历是O(n),第二次遍历是O(1),为常量,所以最后的时间复杂度为O(n),而空间复杂度为O(1)

PS:这个算法很简单,相信大家都会,只是这个题太过于变态了,一般会把面试者吓住

Lv3 码奴
上***水 职业无 6年前#3

O=orgin list

N=[None]*2n
for i in O:

odd=0
even=n
if int(i/2)==i/2:
    N[even]=i
    even+=1
else:
    N[odd]=i
    odd+=1

主要就是空间问题,不占用一个2n的空间应该是不能实现的,因为情况复杂,没法确定常数空间就够用!

Lv3 码奴
上***水 职业无 6年前#4

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.06.md

见其中举一反三中的说明。

论文链接如下

《 STABLE MINIMUM SPACE PARTITIONING IN LINEAR TIME 》

Lv3 码奴
上***水 职业无 6年前#5

这里有一个类似问题的答案:

https://www.quora.com/Given-an-array-of-integers-how-do-I-re-arrange-the-numbers-such-that-odd-numbers-occupy-odd-position-and-even-numbers-occupy-even-position

你这个题解法跟它是相同的,因为要求里只有一处不同:奇数在奇数索引位置,偶数在偶数索引位置。链接里的第一个答案是最接近你想要的答案,为什么说只是接近,是因为它要求原始数组能容纳少量额外数据。

其实我还怀疑,面试官问你的问题,会不会还有隐含条件没跟你讲清楚,比如2n数组本身是个有序数组,情况就大不一样了。

Lv3 码奴
上***水 职业无 6年前#6

刚我赞了@白汀 马上有人踩
可能有人觉得申请了n-1个空间,空间复杂度不是常量。
我用php来输出来验证下,事实上增加的内存是常量,php5.4测试增加内存量为:160

<?php
$arr = range(1,20);  //生成1-20组成的数组
$n = count($arr); //统计数组个数
$old = memory_get_usage(); //统计页面占用内存

/* 开始处理数组 */
for($i=0;$i<$n;$i++){
    if($arr[$i]%2==0){
        $arr[] = $arr[$i];
        unset($arr[$i]);
    }
}
/* 处理结束 */

echo memory_get_usage()-$old; //输出当前占用内存减去原来内存,修改前面数组个数range(1,20),range(1,20000)等,这里输出值固定为:160

var_dump($arr); //输出数组,数组下标到了3n-1,可能会觉得申请了n-1的空间
Lv1 新人
闪***星 UI设计师 6年前#7

有时间复杂度为O(n)的排序吗

上一页12下一页
 文明上网,理性发言!   😉 阿里云幸运券,戳我领取