前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Go 常见算法面试题篇(三):高效调整数组数值顺序

Go 常见算法面试题篇(三):高效调整数组数值顺序

作者头像
学院君
发布2023-03-03 14:12:49
3710
发布2023-03-03 14:12:49
举报
文章被收录于专栏:学院君的专栏学院君的专栏

题目

今天来看一个考察程序员基本功的数组面试题,看起来仍然很简单,不过通过这个题目的不同解法,可以快速检验你是初级程序员还是资深程序员,一起来看下吧:

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

解法一

对于新人而言,可以很快写出下面这样的实现代码:

非常简单,先声明两个数组切片,分别用于存储奇数和偶数,然后遍历待排序的数组切片,根据是否可以被 2 整除将切片数据分发到偶数和奇数切片,最后将偶数切片数据追加到奇数切片之后作为新的切片返回。

为上面这段代码编写测试代码:

执行之后打印结果如下,说明代码可以正常工作:

解法二

上面的实现虽然简单易懂,不过扩展性很差,比如现在是按照奇偶数排序,如果换一下排序条件,变成按照是否可以被3整除,或者按照正负数进行排序,则需要重写整个排序方法实现代码。

实现相同功能的代码,在满足最基本的正确性的基础上,新人和老鸟的区别往往就是体现在扩展性、鲁棒性、高性能这些更高层级的代码艺术上。

下面我们从扩展性的角度出发,将排序条件抽取出来作为可定制的闭包参数从外部传入排序函数:

这样一来,reOrderArrayV2 函数就与具体的排序条件解耦了,我们可以通过外部参数传入任意的排序条件:

打印结果如下,表明排序成功:

下次你想通过正负数、是否可以被3整除之类的排序条件做排序,只需要编写对应的排序条件判定函数,然后传入 reOrderArrayV2排序函数即可,排序函数本身无需做任何调整:

性能对比

从扩展性上看,显然第二种解法比第一种好很多,除此之外,我们在第二种解法中还通过指针移动和位运算的方式优化了程序的性能,具体对性能的影响如何,可以编写基准测试来验证:

运行上面的基准测试代码:

可以看到 reOrderArrayV2 排序函数的单次运行时间要比 reOrderArrayV1 快 6 倍,性能有了很显著的提升。

此外,还可以加上 -benchmem 选项对比下两种解法的内存分配情况(空间复杂度),由于第一种解法需要引入额外的数组切片存储中间数据,所以显然第二种解法的空间复杂度更优:

可以看到,第一种解法每次要分配 368B 的内存空间,而第二种解法不需要额外分配内存空间。

通过上面的对比,你觉得自己是初级程序员还是资深程序员呢?或者你还有没有更优的解法呢?欢迎通过下面的评论框展示你的能力。

(本文完)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-08-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 极客书房 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 解法一
  • 解法二
  • 性能对比
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档