Faster, Higher, Stronger
更快,更高,更强

数字数组奇排序问题

有个网上看到的面试题,在部门群里分享了下然后看了下大家的处理方案,后面又有个同事私发我了一个类似的题目为啥能起到效果,我觉得这个题目本身意义不大,但是讨论过程挺有价值的。于是写作本文。

一、问题

给定一个由数字组成的数组(数组内元素均为大于0的整数),要求将数组中的奇数移动到左边,偶数移动到右边。

二、答案

网上的答案很取巧:

const arr = [1, 2, 3, 4, 5, 6]

arr.sort((a) => -a % 2)

这里要知道当sort内的回调函数返回-1时,参与比较的两个数字a和b的顺序将是a在左边b在右边。在上面的答案里,我们不需要同时比较a和b,只要比较a就可以了,当a为奇数时,-a%2的值为-1,此时不管b的值是多少,a都在左边。这样就可以保证最后的结果里,奇数都在左边了。

我在团队内部分享这个问题的时候,并不是希望大家能回答出来上面的答案,我觉得不刷面试题的话一般人想不到这个答案的。我是想看看大家能否有其他不错的答案。

2.1、方案1

方案:直接创建一个新数组对象,然后对老数组对象进行n*n次嵌套遍历来进行暴力比较。

分析:这样做肯定可以拿到我们想要的结果。但是这显然是最基础的方案,也就是没法给你加分的答案。但是,如果你在遍历时,做到下面两点,是可以有一定加分的。

1、知道外层循环里遍历内层循环时,只用后面的元素来比,而不是每次都和内层循环里的每个元素都比一下;

2、知道拿一个变量来标记每次遍历后是否有元素位置的调整,如果没有的话说明遍历结果已经实现了,可以提前结束嵌套遍历。

另外需要知道,这种嵌套2层的遍历循环,时间复杂度为n^2,还是比较高的。

2.2、方案2

同事有写出来用数组的filter和concat方法操作的,我感觉也可以,起码用了ES6的东西。

arr.filter((item) => item % 2 === 1).concat(arr.filter((item) => item % 2 === 0)

这样写起来比较简单,也很好理解,时间复杂度只有n。非常适合用于业务代码中,换句话说,这是一句非常好的业务代码。我知道有人会说,代码量稍多一点,一个循环里就可以分出来所有奇数和所有偶数了。我觉得那种写法可读性没这个好,而且时间复杂度其实都是n,在业务代码的前提下,上面的还是要更好一些。但是在非业务代码的前提下,肯定是循环一次的方案比循环2次的方案好。

2.3、方案3

还有个同事是用reduce实现的。

arr.reduce((prev, curr) => curr % 2 === 0 ? [...prev, curr] : [curr, ...prev], [])

这个方案我觉得思路和实现都挺好的,个人觉得比方案1和2要好,用到了数组的reduce方法和…。而且这里[…prev, curr]这种写法也是一个亮点。

2.4、方案4

下面这个方案有点意思。

arr.sort((a, b) => (a % 2 === 1 ? a / 9999999 : a) - (b % 2 === 1 ? b / 9999999 : b))

这方案是我提问后,有个同事私聊我发过来问我这个为啥可以实现奇偶分开并且各自排序的。我一看这个应该是有前提条件的,应该是同事漏说了。

这里a和b都有相同的处理逻辑,就是如果是偶数就是本身,如果是奇数就除以9999999。这里9999999不是一个一定要这个值的,其目的只是为了把奇数弄的很小。小到多小呢?因为题目的要求是让奇数显示在左边,偶数在右边,所以要比所有的偶数都小,就是要比最小的偶数要小。大于0的最小偶数是2,所以只要奇数除以9999999小于2即可,所以这里对题目需要增加一个前提条件——数组内的奇数大小要小于9999999 * 2的值

当a和b有一个为奇数有一个为偶数时,因为奇数小于偶数,所以奇数会被排序到偶数的左边。

当a和b同为奇数或者同为偶数时,因为这里对a和b的处理逻辑都是直接乘以一个相同的系数(同时为1/9999999或者1),所以等价于直接比较a和b的大小,小的排前面,大的排后面。

所以,就能实现同时将奇数排到偶数左边,且各自都按从小到大的顺序进行排序了。

如果面试时能主动这样加大题目难度,然后进行回答的话,显然是有拔高面试印象分的作用的。

赞(1) 打赏
转载需注明来源并给出来源页链接:峰间的云 » 数字数组奇排序问题

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏