今天面试遇到的情况

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

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

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

[lcc142625]

这种呢，不能说你的问题，我也遇到过，就是面的时候卡壳想不出来题解，不过那会我面的滴滴的，起码面试官还给我思路，不至于一直两个人尴尬着，有些问题我回头想，能理解也能做出来，但是面试真就紧张，就会怯场，害，这个别太影响你下回面试，每家面试套路都不一样

[cxe2v]

@lcc142625 #1 我这个面试官也是给了我提示我才知道他想要用双指针的，也没有说一直尴尬，因为是在网页上写代码，滴滴我面过，运气好到没有做任何题就直接到了终面然后被 pass 了，运气啊真的是实力的一部分

[carlclone]

啥双指针, 他是想你原地排序吧, O(1)空间复杂度 , 我知道的一个方法是用快排的分区思想, 写起来也不算很简单

[v2webdev]

这题用双指针怎么做？

[carlclone]

@carlclone 看错题目了...

[lcc142625]

emm，运气，看面试官和你对不对眼了，我就是，面试类似走了流程直接过了，莫心焦，我也是面了两个月左右才找到的

[lemon94]

如果面试官没限定你使用内存的空间，那你的解法没什么问题。
如果限定你原地，那你的方法就不行了。

[fiypig]

一般来说解决问题以后再来谈优化，你没错的

[hello2060]

开始写之前多和面试官沟通呗，或者先把思路说一遍，如果是他要的你再开始写。

不过这个题一看你开了新数组应该就不是他要的哈，不然谁都会啊。

类似于快排，一个指针 i 初始化为 0，p=-1,如果偶数 i++，如果是奇数 swap(++p, i); i++
不过他确实要把条件先告诉你，比如不能利用额外空间

[djFFFFF]

即使是不从算法复杂度（常数优化）的角度考虑，你的做法涉及 array 对象创建（还没指定大小，后续可能涉及 array 扩容），cpu 指令数还是比原地排序要多很多的。当然没多到指数级别就是了。
我是面试官的话，我会觉得你能干活，但不抠细节。所以看你面的是什么岗位以及这个岗位的要求是什么了。

[ccvzz]

```javascript
function filter(arr) {
const ret = [...arr];
let lo = 0, hi = 0;
// arr[0:lo] is odd
while (hi < ret.length) {
if (ret[hi] % 2 == 0) {
hi++;
} else {
[ret[lo], ret[hi]] = [ret[hi], ret[lo]];
lo++;
hi++;
}
}
return ret;
}
```

双指针做法，我自己测试了一下貌似没啥问题

[cxe2v]

@djFFFFF #10 你这个说的有道理，原地排序确实省资源，至于面的岗位，面试官也不清楚具体干啥

[djFFFFF]

@cxe2v 那我觉得面试官自己也没想好他的面试方式是否正确，是否能帮公司招到合适的人。

[devfeng]

可能是你面试经验少了，现在都这个套路，给一个算法题，给出最优解才能接着聊。ps.之前面试遇到个差不多的题，也是双指针，要求奇数在奇数位，偶数在偶数位。

[ttys001]

x = [2,1,5,7,4,9,8,5,6]
def odd_even(x: list, l: int, h: int) -> list:
for i in range(l, h):
for j in range(i, h):
if x[j]%2 == 0 and x[j+1]%2 == 1:
x[j], x[j+1] = x[j+1], x[j]
return x
odd_even(x, 0, len(x)-1)
这叫冒泡法嘛？

[chocovon]

我倒是觉得，如果是面对某个性能要求不高的业务问题，你的代码才是好代码，做到了就事论事，没有引入不必要的复杂性

[isRealLeven]

也许是你刷题刷少了。本来题目不难，而且说明了双指针。应该很快就能做出来

[javapythongo]

@ccvzz 题目要求奇偶顺序后，还要求相对奇数 /偶数之间的相对位置大小不能变

[cxe2v]

@isRealLeven #17 对的，就是题刷少了，算法题真的刷得少

[wjploop]

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

[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]

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

[CEBBCAT]

@buffzty 可以发 gist

[CEBBCAT]

@Livid 考虑不考虑检测到两行 ``` 就提示使用 gist ？

[iCineon]

vector<int> sortedArray(vector<int>& nums){
int n=(int)nums.size();
int l=0,r=n-1,i=0;
while (l<r && i<n) {
if (nums[i]%2==0) {
swap(nums[i++], nums[r--]);
}else{
swap(nums[i++], nums[l++]);
}
if (i>=r)break;
}
reverse(nums.begin()+1+l, nums.end());
return nums;
}

[cxe2v]

@linvon #35 你说得对，双指针确实是消耗时间和资源最少的解法，我可能没有那么追求极致吧，我想要的是快速解决问题

[huang119412]

剑指 offer 原题，根本不是考察怎么做出结果，而是要你找到最好的方法，这种没 [背过题 ] 就无了，就是一次快排，不过 pivot 变成了是否是奇偶数。这类还有第 K 个大、小的数。回溯法寻找路径，动态规划找最优值，更不要说那些单调栈、队列的题，不背几乎不可能找到最好的方法。背题对个人没什么太大成长，但是大环境趋势。

[cxe2v]

@huang119412 #45 也不一定说背题没成长吧，背的多见得多了，可能会影响工作中的思维，但是有几个写代码的是需要研究代码最优解如何实现的呢？

[crazyxtcn]

@yazoox 905

[linglongll]

58 同城前端 2 面题 其实你如果灵活点的话可以问问面试官 别头铁硬做 有时候面试官也是考察你的一些交流能力的

[hyq]

我觉得这个题分两部分，一个是排序算法本身，快排，堆排等各种方式。另一个就是考比较函数。
排序算法本身不必说，就那么几种形式，书本上都有。
这个比较函数灵活性就比较大了，楼主那种方式虽然能实现，但没有答到点子上，写个简单的函数，同时判断奇偶与大小就行。

并且在实际中，排序的思路也是这样的，比较函数与排序算法一般都是分开实现的。如果面试官不懂这个道理，就怼他。

a = [1,2,3,4,5,6,7,8]

a.sort((a,b)=> {
if (a==b){return 0}
if(a%2==1 && b%2==0){return -1}
if(a%2 == 0 && b%2 == 1) {return 1}
if (a<b){return -1};
return 1
})

[500miles]

@javapythongo

else 里面的 for 循环可以省掉吗? arr[r] 和 arr[l] 直接交换就可以吧

[javapythongo]

@500miles 应该可以，我以为交换后，还要保证奇 /偶数原来的相对位置，但是这道题应该没有这样要求

[rodrick]

双指针，右边先开始找到第一个奇数，然后左边再找第一个偶数，然后交换这样吧，就是快排的思路，如果需要排序的话还要多加一下判断大小的条件？其实就是个思路问题。。刷过就会没刷过不会很正常，算法这玩意，就当八股文看就行

[teawithlife]

@buffzty #37 我觉得你的思路是对的，但是实现上可能有点问题，比如数据变成
arr := []int{2, 1, 5, 7, 4, 6, 8, 5, 6}
出来的结果就不对了
play.golang.org/p/8nk_2P3ycP2

[M7w2kh5a58AhKlcT]

func sortFilter(nums []int) []int {
j := 0
for i,v := range nums {
if v %2 != 0 {
if i != j {
nums[i],nums[j] = nums[j],nums[i]
}
j++
}
}
return nums
}

go 代码

[xlzpx]

@cxe2v pass 是通过了还是没通过。。。

[cxe2v]

@xlzpx #55 被 pass 了指没通过，passed 代表已通过

[lvzx]

他的目的是想你 O(n)时间 O(1)空间复杂度做出来，你直接开个数组写太简单了，肯定会 follow up 的

[dinghmcn]

类似于快速排序的扫一遍就可以

[roselia]

刚刚在公司的时候我就一直在想到底要怎么样才可以，回家后才做出来，哎，自己的算法真的太差了，很担心明天的面试

```javascript
function sort(array) {
let i = 0;
let left = 0;
let j = array.length - 1;
let right = array.length - 1;

while (left < right && i < array.length && j >= 0) {
while (j >= 0 && array[j] % 2 === 1) {
j--;
}
[array[right], array[j]] = [array[j], array[right]];
right--;
j--;
while (i < array.length && array[i] % 2 === 0) {
i++;
}
[array[left], array[i]] = [array[i], array[left]];
left++;
i++;
}
}
```

总结了一下，确实是快速排序类型的解法

[buffzty]

@teawithlife 不好意思,我的思路是错的.用快排重写了一下. https://play.golang.org/p/MUAdUXXk5_w
但是并不能保证后面偶数的顺序,只能这样了

[waytoexplorewhat]

我怎么觉得你的问题不是双指针，而是沟通，在解决问题之前应该先澄清问题，有什么需求、输入、输出是什么、约束是什么，这些讨论清楚了才应该开始思考问题的解决

[cfwyy]

leetcode 有类似题目。
用 python 来解就一行，直接排序就完了，不知道会不会被鄙视 - -

return sorted(arr,key=lambda x:x%2,reverse=True)

[cxe2v]

@cfwyy #62 会被鄙视，你这跟我写的第二个 function 是一个方法

[cxe2v]

@waytoexplorewhat #61 我想说的重点不是面试，我是想说工作中遇到这种问题，需要抠细节吗？

[iwukong]

国内吗 现在国内面试也全算法啦？

[cxe2v]

@iwukong #65 是的，国内现在稍微好点的厂面试都要面算法了

[lewinlan]

仔细一看根本就没有排序啊只是交换位置而已，肯定是双指针了，如果我是面试官我也不接受其他解法……

[maocat]

```python
class Solution(object):
def sort(self, array):
"""
:param array:
"""
length = len(array)
i, j = 0, length - 1
while i < j:
i2 = array[i] % 2 == 0
j2 = array[j] % 2 == 0
if i2 and j2:
j -= 1
elif not i2 and not j2:
i += 1
elif i2 and not j2:
d = array[i]
array[i] = array[j]
array[j] = d
i += 1
j -= 1
else:
i += 1
j -= 1

```