题目:输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
分析:如果不考虑时间复杂度,最简单的思路应该是从头扫描这个数组,每碰到一个偶数时,拿出这个数字,并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位,这时把该偶数放入这个空位。由于碰到一个偶数,需要移动O(n)个数字,因此总的时间复杂度是O(n2)。
要求的是把奇数放在数组的前半部分,偶数放在数组的后半部分,因此所有的奇数应该位于偶数的前面。也就是说我们在扫描这个数组的时候,如果发现有偶数出现在奇数的前面,我们可以交换他们的顺序,交换之后就符合要求了。
因此我们可以维护两个指针,第一个指针初始化为数组的第一个数字,它只向后移动;第二个指针初始化为数组的最后一个数字,它只向前移动。在两个指针相遇之前,第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数,我们就交换这两个数字。
基于这个思路,我们可以写出如下的代码:
讨论:
上面的代码有三点值得提出来和大家讨论:
1.函数isEven判断一个数字是不是偶数并没有用%运算符而是用&。理由是通常情况下位运算符比%要快一些;
2.这道题有很多变种。这里要求是把奇数放在偶数的前面,如果把要求改成:把负数放在非负数的前面等,思路都是都一样的。
3.在函数Reorder中,用函数指针func指向的函数来判断一个数字是不是符合给定的条件,而不是用在代码直接判断(hard
code)。这样的好处是把调整顺序的算法和调整的标准分开了(即解耦,decouple)。当调整的标准改变时,Reorder的代码不需要修改,只需要提供一个新的确定调整标准的函数即可,提高了代码的可维护性。例如要求把负数放在非负数的前面,我们不需要修改Reorder的代码,只需添加一个函数来判断整数是不是非负数。这样的思路在很多库中都有广泛的应用,比如在STL的很多算法函数中都有一个仿函数(functor)的参数(当然仿函数不是函数指针,但其思想是一样的)。如果在面试中能够想到这一层,无疑能给面试官留下很好的印象。
分享到:
相关推荐
调整数组顺序使奇数位于偶数前面,python,jupyter,调整数组顺序使奇数位于偶数前面,python,jupyter
调整数组顺序使奇数位于偶数前面.md
java基础面试题调整数组顺序使奇数位于偶数前面本资源系百度网盘分享地址
面试题21. 调整数组顺序使奇数位于偶数前面题目链接面试题21. 调整数组顺序使奇数位于偶数前面题目描述输入一个整数数组,实现一个函数来调整该数组中数字的顺序,
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面剑指 Offer 21. 调整数组顺序使奇数位于偶数前面输入一个整数数组,实现一个函数来调整该数组中数字
title: 剑指Offer-调整数组顺序使奇数位于偶数前面subtitle: 调整数组顺序使奇数位于偶数前面categories: 剑指Offer调整数组顺序
调整数组顺序使奇数位于偶数前面题目描述输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
剑指Offer(Python多种思路实现):调整数组的顺序使奇数位于偶数前面 面试21题: 题目:调整数组的顺序使奇数位于偶数前面 题一:输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前...
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。 2、书上的解法(相对位置改变) ...
1 数组 3 1.1 求子数组的最大和 3 ...1.3 调整数组顺序使奇数位于偶数前面 5 1.4 找出数组中两个只出现一次的数字 5 1.5 旋转数组 7 1.6 旋转数组的最小元素 11 1.7 扑克牌的顺子 13 2 树 15 2.1 二叉树的非递归操作 15
面试题14:调整数组顺序使奇数位于偶数前面 面试题18:树的子结构 面试题20:顺时针打印矩阵 面试题21:最小栈 面试题26:复杂链表的复制 面试题31:连续字数组的最大和 面试题32:从1到n的整数中1出现的次数 面试题...
Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为...调整数组顺序使奇数位于偶数前面 905. Sort Array By Parity 链表中倒数第
leetcode中国 LeetCode 刷题记录 分类 二维数组 题目名称 goldhadis Toetoise FlashOpen-Go 对角线遍历 ...调整数组顺序使奇数位于偶数前面 Y Y Y 剑指 Offer 24. 反转链表 Y Y Y 剑指 Offer 25. 合并
13.调整数组顺序使奇数位于偶数前面 14.单链表:链表中倒数第k个结点 15.单链表:反转链表 16.单链表:合并两个排序的链表 17.二叉树:树的子结构 18.二叉树:二叉树的镜像 19.顺时针打印矩阵 20.栈:包含min函数的栈
调整数组顺序使奇数位于偶数前面 代码的完整性 14 链表中倒数第k个结点 代码的鲁棒性 15 反转链表 代码的鲁棒性 LeetCode 206 16 合并两个排序的链表 代码的鲁棒性 17 树的子结构 代码的鲁棒性 18 二叉树的镜像 面试...
调整数组顺序使奇数位于偶数前面 数组中出现次数超过一半的数字 最小的k个数 数组中的第K个最大元素 把数组排成最小的数 存在重复元素 打乱数组 三数之和 化栈为队 144.二叉树的前序遍历 146.LRU缓存机制 155.最小栈...
调整数组顺序使奇数位于偶数前面 链表中倒数第 k 个节点 - [移除单链表倒数第 n 个节点] - leetcode 19 反转链表 - [反转单链表] - leetcode 206 合并两个排序的链表 - [合并两个有序链表]- leetcode 21 树的子结构 ...
Interviews(剑指offer Java代码)二维数组中的查找替换空格从尾到头打印链表重建二叉树用两个栈实现队列旋转数组的最小数字斐波那契数列跳台阶变态跳台阶矩形覆盖二进制中1的个数数值的整数次方调整数组顺序使奇数...