今天面试遇到的情况

今天面了一家做笔记的厂，是手写代码面，第一个题就是奇偶排序的问题，题目如下

input: [2,1,5,7,4,9,8,5,6] output: [1,5,7,9,5,2,4,8,6]

输入一个整数数组，期望输出的数组里，奇数在前边，偶数在后边

我想这不简单么，我有好几种办法可以实现这个功能，然后我就写下了如下代码

    function filter(originArray) {
        let oddArray = [];
        let evenArray = [];
        originArray.forEach(item => {
            if (item % 2 == 1) {
                oddArray.push(item);
            }
            else {
                evenArray.push(item);
            }
        })
        return oddArray.concat(evenArray);
    }

其实我还有以下办法可以实现

    function filter(originArray) {
        originArray.sort((a, b) => {
            return b % 2 - a % 2;
        })
        return originArray;
    }

    function filter(originArray) {
        return originArray.filter(a => {
            return a % 2 == 1;
        }).concat(originArray.filter(b => {
            return b % 2 == 0;
        }));
    }

但是我没想到，面试官其实是想考察双指针排序的变种，我对这种双指针得问题本来就不熟，就卡在这问题上搞了 20 来分钟，整得我都没脾气了，汗都整出来了，后面又考察了一个问题，我只知道原理，让我手写又一次写错，就尴尬地结束了这一次面试。

可能刚好对方的实际项目中需要解决这类算法的问题，面试没面好是我的问题，

我想说的是，对于一个问题，没能按面试官想的方式解决，是不是就算活不好了？

wjploop

2021-01-28 18:08:53 +08:00

理解题意确实很重要，咋一看我以为“奇数序列”和“偶数序列”要求有序，若是这样，改变了“两个数的比较规则”而已，用常用的排序方法就行，时间复杂度必然大于等于 nlogn （不考虑桶排序）。
既然没有要求，时间复杂度就可以降到 O(n)了，作为面试题，这题的应该隐含了一个硬性要求“空间复杂度为 O(1)”。那么，确实是用双指针的做法了。简单的思路就是，
假设目标序列为左边奇数右边偶数，
设立左右指针，左指针指向 0，右指针指向 len - 1
左指针往右移动一直遇到偶数停住 i，右指针往左移动直到遇到奇数停住 i，交换这两位置的数
不断重复以上操作，直到两指针相遇结束