今天面试遇到的情况

[cxe2v]

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

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 来分钟，整得我都没脾气了，汗都整出来了，后面又考察了一个问题，我只知道原理，让我手写又一次写错，就尴尬地结束了这一次面试。

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

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

[javapythongo]

这样子吗？
```java
public static void main(String[] args) {
int[] arr = {2, 1, 5, 7, 4, 9, 8, 5, 6};
int l = 0;
int r = 0;
while (r < arr.length) {
if (arr[r] % 2 == 0) {
r++;
} else {
int odd = arr[r];
for (int i = r; i > l; i--) {
arr[i] = arr[i - 1];
}
arr[l] = odd;
l++;
r++;

}
}
System.out.println(Arrays.toString(arr));
}
```

[javapythongo]

感觉我写的这个还不如你的空间换时间

[crazyxtcn]

@javapythongo 我觉得这个问题很重要，我开始以为输出要求不改变在原数组中的相对位置，然后在 leetcode 上搜了一下，发现有原题，没要求相对位置，不要求相对位置就很简单了

[ezksdo]

这和快排有啥区别，直接让比较函数偶数比基数大不就行了吗

[YouLMAO]

排序个 jb，2 个 for 循环，先打奇数再打偶数，6 行代码，最优的时间和空间复杂度

[YouLMAO]

出题的人连最优算法都不知道，指针个屁

[chienius]

双路快速排序了解一下，其实就是快排分区算法

[mccreefei]

快排 partition 思路
```java
public int[] sort(int[] data) {
int left = 0 , right = data.length - 1, cur = 0;
while (cur < right) {
if (data[cur] % 2 == 1) {
swap(data, cur++, left++);
} else {
swap(data, cur, right--);
}
}
return data;

}
private void swap(int[] data, int i, int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
```

[onyourroad]

多刷点 leetcode 就好了。

[yazoox]

@crazyxtcn 题目编号是？

[wjploop]

@crazyxtcn 要是还有条件要求排序稳定（排序后相对位置不变），得牺牲空间或时间吧。牺牲空间就是楼主的做法了，牺牲时间可以用插入排序，时间复杂度要 n 平方了

[lwlizhe]

话说这题要不要排序啊，

比如说 {2,1,5,7,4,9,8,5,6} 这串

正确答案应该是{1，5，5，7，9，2，4，6，8}

要排序的话，好像所有人都做错了

[lwlizhe]

@lwlizhe 好吧，确实有人问了下奇偶相对的问题……当我没说

[e583409]

面试的目的是什么？

[linvon]

首先这就是个奇偶区分的问题，不是什么排序，双指针是最简单的解法，快排啥的就扯远了
其次从性能上来说，你的解法确实存在些问题，不如自己分析一下各种解法的时间和空间复杂度。
算法面试就是这样，不服的话也没办法，啃吧

[kiripeng]

给他整个三路排序

[buffzty]

我记得没错的话快排里有用到跟原地排序的算法.
你这个题没有要求奇偶数组再排序 只要 2 个循环就好了
1. 遍历数组将奇数顺序放到头部,偶数逆序放到尾部
2. 遍历偶数数组 并翻转
```go
package main

import "fmt"

func main() {
arr := []int{2, 1, 5, 7, 4, 9, 8, 5, 6}
length := len(arr)
head := 0
tail := length - 1
for i := 0; i < tail; i++ {
if arr[i]&1 == 1 {
arr[i], arr[head] = arr[head], arr[i]
head++
} else {
arr[i], arr[tail] = arr[tail], arr[i]
tail--
}
}
tail--
for i := length - 1; i > tail; i-- {
arr[i], arr[tail] = arr[tail], arr[i]
tail++
}
fmt.Println(arr)
}
```

[buffzty]

不能直接发代码是真的恶心.交流体验极差

[hello2060]

@linvon 快排没问题啊，线性复杂度，三行代码，而且能保证左边部分的相对顺序。

[kx5d62Jn1J9MjoXP]

说实话我觉得这个题挺好，难度不太高不至于面试时紧张想不出来，又对基础有一定考察