一个js面试题

Question

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

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

于是我这样：

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

所以该怎么做呢?

Answer 1

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

Answer 2

let A = arr=>arr.sort(x=>x % 2 == 0)

Answer 3

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)

Answer 4

不解为什么都是这种答案，根本实现不了

这种测试可以

而且规定返回1，-1，0 才会移动元素啊

arr.sort(function(a, b) {
    //首先判断满足a是偶数b是奇数
    if(a % 2 == 0 && b % 2 == 1) {
        return 1;
    }
    return -1;
})

Answer 5

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

Answer 6

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

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

Answer 7

我感觉排序可能还得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])

Answer 8

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

Answer 9

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

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

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

还有第二种操作，但是要注意溢出问题的存在：
a = a + b;
b = a - b;
a = a - b;

Answer 10

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

Answer 11

var arr = [1, 4, 2, 5, 6, 8, 9];
console.log(changeArr(arr));

function changeArr(arr) {
    var newArr = [];
    for(var i = 0, length = arr.length; i < length; i++) {
    if(arr[i] % 2) {
           newArr.push(arr[i]); //往后添加
        } else {
            newArr.unshift(arr[i]); //往前添加
        }
    }
    return newArr;
}