一、前言
本系列文章为《剑指Offer》刷题笔记。
刷题平台:牛客网
书籍下载:共享资源
二、题目
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
1、思路
创建双向队列,遍历数组,奇数前插入,偶数后插入。最后使用assign方法实现不同容器但相容的类型赋值。
2、代码
C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution { public: void reOrderArray(vector<int> &array) { deque<int> result; int num = array.size(); for(int i = 0; i < num; i++){ if(array[num - i - 1] % 2 == 1){ result.push_front(array[num - i - 1]); } if(array[i] % 2 == 0){ result.push_back(array[i]); } } array.assign(result.begin(),result.end()); } }; |
Python2.7:
双向队列:
1 2 3 4 5 6 7 8 9 10 11 12 13 | # -*- coding:utf-8 -*- from collections import deque class Solution: def reOrderArray(self, array): # write code here odd = deque() l = len(array) for i in range(l): if array[l-i-1] % 2 != 0: odd.appendleft(array[-i-1]) if array[i] % 2 == 0: odd.append(array[i]) return list(odd) |
列表:
1 2 3 4 5 6 7 8 9 10 11 12 | # -*- coding:utf-8 -*- class Solution: def reOrderArray(self, array): # write code here res = [] l = len(array) for i in range(l): if array[l-i-1] % 2 != 0: res.insert(0,array[-i-1]) if array[i] % 2 == 0: res.append(array[i]) return res |
不开辟新空间:
1 2 3 4 5 6 7 8 9 10 | # -*- coding:utf-8 -*- class Solution: def reOrderArray(self, array): # write code here boarder = -1 for idx in range(len(array)): if array[idx] % 2: boarder += 1 array.insert(boarder, array.pop(idx)) return array |
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
2018年7月20日 上午11:16 沙发
c.assign(beg,end):将[beg; end)区间中的数据赋值给c。
2019年3月20日 下午4:20 板凳
这道题如果不借助辅助队列,使用插入排序是不是更好:
void reOrderArray(int arr[], int len) {
for (int i = 0; i 0; j–) {
if (arr[j-1]%2 == 1)
break;
int tmp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = tmp;
}
}
}
2019年3月20日 下午8:30 1层
@董明高
2019年3月20日 下午8:32 2层
@Jack Cui 哈哈,我贴的代码不知道为什么不能正常显示
2019年3月20日 下午10:16 3层
@董明高 正常留言区我没有设置代码样式。