今天面试遇到的情况

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

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

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

[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

[nnd]

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
但是并不能保证后面偶数的顺序,只能这样了