今天面试遇到的情况

    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;         }));     } 

• 資深大佬 : 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 快排没问题啊，线性复杂度，三行代码，而且能保证左边部分的相对顺序。

• 資深大佬 : ssynhtn

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

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

• 資深大佬 : 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

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