这是一个创建于 1767 天前的主题，其中的信息可能已经有所发展或是发生改变。
今天面了一家做笔记的厂，是手写代码面，第一个题就是奇偶排序的问题，题目如下
input: [2,1,5,7,4,9,8,5,] 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 来分钟，整得我都没脾气了，汗都整出来了，后面又考察了一个问题，我只知道原理，让我手写又一次写错，就尴尬地结束了这一次面试。
可能刚好对方的实际项目中需要解决这类算法的问题，面试没面好是我的问题，
我想说的是，对于一个问题，没能按面试官想的方式解决，是不是就算活不好了？
 | 1 lcc142625 2021-01-28 17:07:03 +08:00 这种呢，不能说你的问题，我也遇到过，就是面的时候卡壳想不出来题解，不过那会我面的滴滴的，起码面试官还给我思路，不至于一直两个人尴尬着，有些问题我回头想，能理解也能做出来，但是面试真就紧张，就会怯场，害，这个别太影响你下回面试，每家面试套路都不一样 |
 | 2 cxe2v OP @lcc142625 #1 我这个面试官也是给了我提示我才知道他想要用双指针的，也没有说一直尴尬，因为是在网页上写代码，滴滴我面过，运气好到没有做任何题就直接到了终面然后被 pass 了，运气啊真的是实力的一部分 |
 | 3 carlclone 2021-01-28 17:13:34 +08:00 啥双指针, 他是想你原地排序吧, O(1)空间复杂度 , 我知道的一个方法是用快排的分区思想, 写起来也不算很简单 |
 | 4 v2webdev 2021-01-28 17:14:22 +08:00 这题用双指针怎么做？ |
| 6 lcc142625 2021-01-28 17:19:12 +08:00 emm，运气，看面试官和你对不对眼了，我就是，面试类似走了流程直接过了，莫心焦，我也是面了两个月左右才找到的 |
 | 7 lemon94 2021-01-28 17:24:50 +08:00  1 如果面试官没限定你使用内存的空间，那你的解法没什么问题。 如果限定你原地，那你的方法就不行了。 |
 | 8 fiypig 2021-01-28 17:28:22 +08:00 via iPhone 一般来说解决问题以后再来谈优化，你没错的 |
 | 9 hello2060 2021-01-28 17:29:57 +08:00 via iPhone 1 开始写之前多和面试官沟通呗，或者先把思路说一遍，如果是他要的你再开始写。 不过这个题一看你开了新数组应该就不是他要的哈，不然谁都会啊。 类似于快排，一个指针 i 初始化为 0，p=-1,如果偶数 i++，如果是奇数 swap(++p, i); i++ 不过他确实要把条件先告诉你，比如不能利用额外空间 |
 | 10 djFFFFF 2021-01-28 17:38:59 +08:00 即使是不从算法复杂度（常数优化）的角度考虑，你的做法涉及 array 对象创建（还没指定大小，后续可能涉及 array 扩容），cpu 指令数还是比原地排序要多很多的。当然没多到指数级别就是了。 我是面试官的话，我会觉得你能干活，但不抠细节。所以看你面的是什么岗位以及这个岗位的要求是什么了。 |
 | 11 0xo 2021-01-28 17:39:52 +08:00 1 ```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; } ``` 双指针做法，我自己测试了一下貌似没啥问题 |
 | 14 devfeng 2021-01-28 17:55:26 +08:00 via Android 可能是你面试经验少了，现在都这个套路，给一个算法题，给出最优解才能接着聊。ps.之前面试遇到个差不多的题，也是双指针，要求奇数在奇数位，偶数在偶数位。 |
 | 15 ttys001 2021-01-28 17:56:53 +08:00 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) 这叫冒泡法嘛？ |
 | 16 chocovon 2021-01-28 17:59:43 +08:00 1 我倒是觉得，如果是面对某个性能要求不高的业务问题，你的代码才是好代码，做到了就事论事，没有引入不必要的复杂性 |
 | 17 isRealLeven 2021-01-28 18:03:24 +08:00 也许是你刷题刷少了。本来题目不难，而且说明了双指针。应该很快就能做出来 |
 | 18 javapythongo 2021-01-28 18:04:29 +08:00 @ccvzz 题目要求奇偶顺序后，还要求相对奇数 /偶数之间的相对位置大小不能变 |
| 19 cxe2v OP @isRealLeven #17 对的，就是题刷少了，算法题真的刷得少 |
 | 20 wjploop 2021-01-28 18:08:53 +08:00  4 理解题意确实很重要，咋一看我以为“奇数序列”和“偶数序列”要求有序，若是这样，改变了“两个数的比较规则”而已，用常用的排序方法就行，时间复杂度必然大于等于 nlogn （不考虑桶排序）。 既然没有要求，时间复杂度就可以降到 O(n)了，作为面试题，这题的应该隐含了一个硬性要求“空间复杂度为 O(1)”。 那么，确实是用双指针的做法了。简单的思路就是， 假设目标序列为左边奇数右边偶数， 设立左右指针，左指针指向 0， 右指针指向 len - 1 左指针往右移动一直遇到偶数停住 i，右指针往左移动直到遇到奇数停住 i，交换这两位置的数 不断重复以上操作，直到两指针相遇结束 |
| 21 javapythongo 2021-01-28 18:23:35 +08:00 这样子吗？ ```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)); } ``` |
| 22 javapythongo 2021-01-28 18:24:43 +08:00 感觉我写的这个还不如你的空间换时间 |
 | 23 crazyxtcn 2021-01-28 18:25:31 +08:00 @javapythongo 我觉得这个问题很重要，我开始以为输出要求不改变在原数组中的相对位置，然后在 leetcode 上搜了一下，发现有原题，没要求相对位置，不要求相对位置就很简单了 |
 | 24 ezksdo 2021-01-28 18:30:59 +08:00 via iPhone 1 这和快排有啥区别，直接让比较函数偶数比基数大不就行了吗 |
 | 25 YouLMAO 2021-01-28 18:32:43 +08:00 via Android 排序个 jb，2 个 for 循环，先打奇数再打偶数，6 行代码，最优的时间和空间复杂度 |
| 26 YouLMAO 2021-01-28 18:33:54 +08:00 via Android 出题的人连最优算法都不知道，指针个屁 |
 | 27 双路快速排序了解一下，其实就是快排分区算法 |
 | 28 mccreefei 2021-01-28 19:14:28 +08:00 快排 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; } ``` |
 | 29 onyourroad 2021-01-28 19:17:28 +08:00 多刷点 leetcode 就好了。 |
| 31 wjploop 2021-01-28 19:51:49 +08:00 @crazyxtcn 要是还有条件要求排序稳定（排序后相对位置不变），得牺牲空间或时间吧。牺牲空间就是楼主的做法了，牺牲时间可以用插入排序，时间复杂度要 n 平方了 |
 | 32 lwlizhe 2021-01-28 20:12:15 +08:00 话说这题要不要排序啊， 比如说 {2,1,5,7,4,9,8,5,6} 这串 正确答案应该是{1，5，5，7，9，2，4，6，8} 要排序的话，好像所有人都做错了 |
 | 34 e583409 2021-01-28 21:04:02 +08:00 面试的目的是什么？ |
 | 35 linvon 2021-01-28 21:43:48 +08:00 1 首先这就是个奇偶区分的问题，不是什么排序，双指针是最简单的解法，快排啥的就扯远了 其次从性能上来说，你的解法确实存在些问题，不如自己分析一下各种解法的时间和空间复杂度。 算法面试就是这样，不服的话也没办法，啃吧 |
 | 36 kiripeng 2021-01-28 22:13:22 +08:00 给他整个三路排序 |
 | 37 buffzty 2021-01-28 22:14:17 +08:00 我记得没错的话快排里有用到跟原地排序的算法. 你这个题没有要求奇偶数组再排序 只要 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) } ``` |
| 38 buffzty 2021-01-28 22:15:21 +08:00 1 不能直接发代码是真的恶心.交流体验极差 |
 | 40 kx5d62Jn1J9MjoXP 2021-01-28 22:44:05 +08:00 via Android 说实话我觉得这个题挺好，难度不太高不至于面试时紧张想不出来，又对基础有一定考察 |
 | 43 iCineon 2021-01-29 08:46:54 +08:00 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; } |
 | 45 huang119412 2021-01-29 09:37:03 +08:00 剑指 offer 原题，根本不是考察怎么做出结果，而是要你找到最好的方法，这种没 [背过题 ] 就无了，就是一次快排，不过 pivot 变成了是否是奇偶数。这类还有第 K 个大、小的数。回溯法寻找路径，动态规划找最优值，更不要说那些单调栈、队列的题，不背几乎不可能找到最好的方法。背题对个人没什么太大成长，但是大环境趋势。 |
| 46 cxe2v OP @huang119412 #45 也不一定说背题没成长吧，背的多见得多了，可能会影响工作中的思维，但是有几个写代码的是需要研究代码最优解如何实现的呢？ |
 | 48 linglongll 2021-01-29 10:23:51 +08:00 58 同城前端 2 面题 其实你如果灵活点的话可以问问面试官 别头铁硬做 有时候面试官也是考察你的一些交流能力的 |
 | 49 hyq 2021-01-29 10:46:32 +08:00 我觉得这个题分两部分，一个是排序算法本身，快排，堆排等各种方式。另一个就是考比较函数。 排序算法本身不必说，就那么几种形式，书本上都有。 这个比较函数灵活性就比较大了，楼主那种方式虽然能实现，但没有答到点子上，写个简单的函数，同时判断奇偶与大小就行。 并且在实际中，排序的思路也是这样的，比较函数与排序算法一般都是分开实现的。如果面试官不懂这个道理，就怼他。 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 }) |
 | 50 500miles 2021-01-29 10:59:51 +08:00 |
| 51 javapythongo 2021-01-29 11:56:31 +08:00 @500miles 应该可以，我以为交换后，还要保证奇 /偶数原来的相对位置，但是这道题应该没有这样要求 |
 | 52 rodrick 2021-01-29 13:06:40 +08:00 双指针，右边先开始找到第一个奇数，然后左边再找第一个偶数，然后交换这样吧，就是快排的思路，如果需要排序的话还要多加一下判断大小的条件？其实就是个思路问题。。刷过就会没刷过不会很正常，算法这玩意，就当八股文看就行 |
 | 53 teawithlife 2021-01-29 13:44:42 +08:00 @buffzty #37 我觉得你的思路是对的，但是实现上可能有点问题，比如数据变成 arr := []int{2, 1, 5, 7, 4, 6, 8, 5, 6} 出来的结果就不对了 play.golang.org/p/8nk_2P3ycP2 |
 | 54 M7w2kh5a58AhKlcT 2021-01-29 13:45:13 +08:00 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 代码 |
 | 57 lvzx 2021-01-29 17:35:20 +08:00 他的目的是想你 O(n)时间 O(1)空间复杂度做出来，你直接开个数组写太简单了，肯定会 follow up 的 |
 | 58 dinghmcn 2021-01-29 17:52:06 +08:00 via Android 类似于快速排序的扫一遍就可以 |
 | 59 roselia 2021-01-29 19:21:00 +08:00 刚刚在公司的时候我就一直在想到底要怎么样才可以，回家后才做出来，哎，自己的算法真的太差了，很担心明天的面试 ```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++; } } ``` 总结了一下，确实是快速排序类型的解法 |
| 60 buffzty 2021-01-29 22:59:54 +08:00 |
 | 61 waytoexplorewhat 2021-01-30 01:38:12 +08:00 via Android 我怎么觉得你的问题不是双指针，而是沟通，在解决问题之前应该先澄清问题，有什么需求、输入、输出是什么、约束是什么，这些讨论清楚了才应该开始思考问题的解决 |
 | 62 cfwyy 2021-01-30 09:42:57 +08:00 leetcode 有类似题目。 用 python 来解就一行，直接排序就完了，不知道会不会被鄙视 - - return sorted(arr,key=lambda x:x%2,reverse=True) |
| 64 cxe2v OP @waytoexplorewhat #61 我想说的重点不是面试，我是想说工作中遇到这种问题，需要抠细节吗？ |
 | 65 iwukong 2021-01-30 14:14:20 +08:00 国内吗 现在国内面试也全算法啦？ |
 | 67 lewinlan 2021-01-31 23:33:39 +08:00 via Android 仔细一看根本就没有排序啊只是交换位置而已，肯定是双指针了，如果我是面试官我也不接受其他解法…… |
 | 68 maocat 2021-02-01 14:19:57 +08:00 ```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 ``` |
Select Language