事情是这样的,作为一个应届生小菜,前些天去人人网面试了
面试官给出了一个题:js实现:一个数组,把奇数放到右边,偶数放到左边,不许使用额外空间。
于是我开始思考,其实如果能使用额外空间的话,额外申请一个数组,根本不是问题。
也想过类似于排序的交换方法,可是交换也需要额外的临时变量tmp不是咩?
而且js好像也没有类似于C语言swap的方法啊
于是我这样:

但是面试官边玩手机边用余光瞥了一眼,继续玩手机,然后又瞥了一眼,终于开口说:你知道从数组中间删除一个元素,splice的运行代价有多大吗?
所以该怎么做呢?
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
一句话
arr.sort(function(a,b){return a%2!==0})可不可以这样:数组前面加入元素用unshift(),
数组后面加入元素用push()。
搞2个索引 一个从0开始,一个从数组最后一个元素开始
找到左边的第一个奇数 右边的第一个偶数交换就可以了
不断循环 直到左边的索引大于右边的
我感觉排序可能还得nlog(n),题目也没要求必须有序, 直接一个循环也可以啊。
至于空间,可以使用位操作不占多余空间, 或者就是简单swap,固定数量的空间(而不是n)应该可以看成不使用额外空间
不申请额外空间使两个数^几次是不是也可以啊
233333,今天上汇编课刚好看到这种不用额外空间的交换,就是上边几位说的这种异或操作的方式,假设有两个变量a,b,交换ab就可以用这样的方式:
此算法能够实现是由异或运算的特点决定的,通过异或运算能够使数据中的某些位翻转,其他位不变。这就意味着任意一个数与任意一个给定的值连续异或两次,值不变。
sort(function(a,b){return a%2})