剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - leetcode 剑指offer系列
发布日期:2021-06-29 07:11:59
浏览次数:4
分类:技术文章
本文共 1822 字,大约阅读时间需要 6 分钟。
题目难度: 简单
今天继续更新剑指 offer 系列, 这道题比较简单, 但同样有多种方法, 大家可以想想看有哪些思路
老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。
- 1 <= nums.length <= 50000
- 1 <= nums[i] <= 10000
题目样例
示例
输入
nums = [1,2,3,4]
输出
[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。
题目思考
- 如何一次遍历搞定?
- 可以不使用额外空间, 直接原地修改吗?
解决方案
方案 1
思路
分析
- 分析题目, 我们要使得奇数在偶数后面, 那么只要保证所有奇数下标都从 0 开始, 而偶数下标从末尾往前即可
- 所以一个很自然的思路就是新建一个数组, 长度和当前一样
- 然后维护两个下标代表新数组的奇数和偶数当前下标
- 最后遍历原数组:
- 遇到奇数就放到新数组的奇数下标处, 同时下标右移
- 遇到偶数就放到新数组的偶数下标处, 同时下标左移
实现
- 下面代码完全基于上述分析实现, 必要步骤都有详细注释
复杂度
- 时间复杂度
O(N)
- 只需要遍历一遍数组
- 空间复杂度
O(N)
- 额外需要一个数组存 N 个元素
代码
class Solution: def exchange(self, nums: List[int]) -> List[int]: odd, even = 0, len(nums) - 1 res = [0] * len(nums) for n in nums: if n & 1: # 当前是奇数, 存到新数组奇数下标处, 同时下标右移 res[odd] = n odd += 1 else: # 当前是偶数, 存到新数组偶数下标处, 同时下标左移 res[even] = n even -= 1 return res
方案 2
思路
分析
- 回顾方案 1, 我们需要额外使用一个数组保存新的数字, 那有没有可能原地修改呢?
- 答案也是可以的, 我们仍然借鉴方案 1 的思路, 只不过这次两个下标对应的是原数组的下标
- 其中左边的下标用于找当前往后第一个偶数, 而右边下标是从后往前第一个奇数, 这样只需要将它们两个交换位置, 就满足奇数在前偶数在后的要求
- 然后两下标继续往中间靠拢, 重复上述步骤即可
实现
- 下面代码完全基于上述分析实现, 必要步骤都有详细注释
复杂度
- 时间复杂度
O(N)
- 每个数字只需要被遍历一遍
- 空间复杂度
O(1)
- 只需要几个变量
代码
class Solution: def exchange(self, nums: List[int]) -> List[int]: i, j = 0, len(nums) - 1 while i < j: while i < j and nums[i] & 1: # 如果当前本身就是奇数, 继续往后找 i += 1 while i < j and nums[j] & 1 == 0: # 如果当前本身就是偶数, 继续往前找 j -= 1 if i < j: # 找到一对不满足条件的奇偶数, 交换它们位置 nums[i], nums[j] = nums[j], nums[i] i += 1 j -= 1 return nums
大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
转载地址:https://blog.csdn.net/zjulyx1993/article/details/107129324 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月18日 14时33分00秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
kangle https设置
2019-04-29
Linux下EasyPanel版本安装及升级
2019-04-29
raspberry pi(树莓派) + easycap d60 视频采集
2019-04-29
WebRTC
2019-04-29
rfc5766-turn-server NAT
2019-04-29
webrtc详细教程
2019-04-29
Android IOS WebRTC 音视频开发总结
2019-04-29
报表图表样式
2019-04-29
支付宝
2019-04-29
Android开发资源收集
2019-04-29
android模板图例
2019-04-29
树莓派网线直连
2019-04-29
复合材料培训(I第七期)
2019-04-29
复合材料生活中的应用
2019-04-29
ABAQUS复合材料(适合小白)
2019-04-29
ABAQUS高级案例解析
2019-04-29
人工智能药物研发
2019-04-29
【超级干货+福利】AIDD最全面的学习教程
2019-04-29
最新通知:AIDD与网络药理学资料大全
2019-04-29