javascript - 一个js面试题
阿神
阿神 2017-04-11 12:50:13
[JavaScript讨论组]

事情是这样的,作为一个应届生小菜,前些天去人人网面试了
面试官给出了一个题:js实现:一个数组,把奇数放到右边,偶数放到左边,不许使用额外空间。

于是我开始思考,其实如果能使用额外空间的话,额外申请一个数组,根本不是问题。
也想过类似于排序的交换方法,可是交换也需要额外的临时变量tmp不是咩?
而且js好像也没有类似于C语言swap的方法啊

于是我这样:


但是面试官边玩手机边用余光瞥了一眼,继续玩手机,然后又瞥了一眼,终于开口说:你知道从数组中间删除一个元素,splice的运行代价有多大吗?

所以该怎么做呢?

阿神
阿神

闭关修行中......

全部回复(9)
伊谢尔伦

一句话arr.sort(function(a,b){return a%2!==0})

ringa_lee
let A = arr=>arr.sort(x=>x % 2 == 0)
迷茫
Array.prototype.swap = function(a, b) {
    this[a] ^= this[b];
    this[b] ^= this[a];
    this[a] ^= this[b];
}
Array.prototype.OddSort = function() {
    for (var i = this.length - 1; i > 0; --i) {
        for (var j = 0; j < i; ++j)
            if (this[j] & 1)
                this.swap(j, j + 1);
    }
}
var arr = [2, 4, 77, 788, 2, 0, 99, 10];
arr.OddSort();
console.log(arr)
迷茫

可不可以这样:数组前面加入元素用unshift(),
数组后面加入元素用push()。

高洛峰

搞2个索引 一个从0开始,一个从数组最后一个元素开始

找到左边的第一个奇数 右边的第一个偶数交换就可以了
不断循环 直到左边的索引大于右边的

PHPz

我感觉排序可能还得nlog(n),题目也没要求必须有序, 直接一个循环也可以啊。
至于空间,可以使用位操作不占多余空间, 或者就是简单swap,固定数量的空间(而不是n)应该可以看成不使用额外空间

function sepEO(nums){
    var e = 0; 
    var o = nums.length-1;
    while(e<o){
        if(nums[e]%2 ==0 ){
            e++;
        }else {
            var tmp = nums[e];
            nums[e]= nums[o]; 
            nums[o] = tmp;
            o--;
        }
    }
    console.log(nums);
}
sepEO([1,3,5,7,9,2,4,6,8,10])
PHPz

不申请额外空间使两个数^几次是不是也可以啊

迷茫

233333,今天上汇编课刚好看到这种不用额外空间的交换,就是上边几位说的这种异或操作的方式,假设有两个变量a,b,交换ab就可以用这样的方式:

a=a^b
b=b^a
a=a^b

此算法能够实现是由异或运算的特点决定的,通过异或运算能够使数据中的某些位翻转,其他位不变。这就意味着任意一个数与任意一个给定的值连续异或两次,值不变。

高洛峰

sort(function(a,b){return a%2})

热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新 English
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号