带你快速刷完67道剑指offer
这是六则或许对你有些许帮助的信息:
⭐️1、阿秀与朋友合作开发了一个编程资源网站，目前已经收录了很多不错的学习资源和黑科技（附带下载地址），如过你想要寻求合适的编程资源，欢迎体验以及推荐自己认为不错的资源，众人拾柴火焰高，我为人人，人人为我🔥！
2、👉23年5月份阿秀从字节跳动离职跳槽到某外企期间，为方便自己找工作，增加上岸几率，我自己从0开发了一个互联网中大厂面试真题解析网站，包括两个前端和一个后端。能够定向查看某些公司的某些岗位面试真题，比如我想查一下行业为互联网，公司为字节跳动，考察岗位为后端，考察时间为最近一年之类的面试题有哪些？
网站地址：InterviewGuide大厂面试真题解析网站。点此可以查看该网站的视频介绍：B站视频讲解 如果可以的话求个B站三连，感谢！ 3、😊 分享一个学弟发给我的20T网盘资源合集，点此白嫖，主要是各类高清影视、电视剧、音乐、副业、纪录片、英语四六级考试、考研考公等资源。4、😍免费分享阿秀个人学习计算机以来收集到的免费学习资源，点此白嫖；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏
5、🚀如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人踩过的坑和留下的经验，事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。
6、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子，一个人踽踽独行不如一群人报团取暖，圈子里沉淀了很多过去21/22/23届学长学姐的经验和总结，好好跟着走下去的，最后基本都可以拿到不错的offer！此外，每周都会进行精华总结和分享！如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话，可以点此下载 。
# No13、调整数组顺序使奇数位于偶数前面
# 题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
# 1、暴力解法，新开辟一个数组保存数据
void reOrderArray(vector<int>& array) {
vector<int> temp(array.size(), 0);
int low = 0;
for (int i = 0; i < array.size(); ++i) {
if ((array[i] & 1) == 1) { temp[low++] = array[i]; }
}
for (int i = 0; i < array.size(); ++i) {
if ((array[i] & 1) == 0) { temp[low++] = array[i]; }
}
array.assign(temp.begin(), temp.end());
}
2
3
4
5
6
7
8
9
10
11
12
13
14
# 2、一种很巧妙的解法，空间复杂度o1的做法，时间复杂度是on^2
void reOrderArray(vector<int>& array) {
for (int i = 0; i < array.size(); i++)
{
//for (auto a : array) {
// cout << a << " ";
//}
cout << endl;
for (int j = array.size() - 1; j > i; j--)
{
if (array[j] % 2 == 1 && array[j-1] % 2 == 0) //前偶后奇就进行交换，这样一趟下来可以将第一个奇数放在首位，同时最后一个偶数放在末尾
{
swap(array[j], array[j - 1]);
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 3、时间和空间都是on的做法，只保存偶数部分
void reOrderArray(vector<int> &array) {
vector<int> temp(array.size(), 0);
int oddIndex = 0, evenIndex = 0;
for (auto a : array) {
if ((a & 1) == 1) array[oddIndex++] = a;
else
temp[evenIndex++] = a;
}
for (int i = 0; i < evenIndex; ++i)
array[oddIndex + i] = temp[i];
}
2
3
4
5
6
7
8
9
10
11
12
# 二刷：
# 1、笨方法另外开辟一个数组，先保存奇数，再保存偶数
void reOrderArray(vector<int> &array) {
int len = array.size();
if(len <= 1) return;
int index = 0;
vector<int> temp(len,0);
for(int i=0;i<len;++i){
if(array[i] %2 == 1) temp[index++] = array[i];
}
for(int i=0;i<len;++i){
if(array[i] %2 == 0) temp[index++] = array[i];
}
array.assign(temp.begin(), temp.end());
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 2、一种原地解法，很巧妙，从后向前进行修正，类似于冒泡法，同时对一刷的时候进行改进
运行时间：2ms 占用内存：480k
void reOrderArray(vector<int> &array) {
int len = array.size();
if (len <= 1) return;
for (int i = 0; i <= len/2; ++i) {
for (int j = len - 1; j > i; --j) {
if ( (array[j]&1) == 1 && (array[j - 1]&1) == 0) swap(array[j], array[j - 1]);//前偶后奇就进行交换，并且一次就可以固定最前面的奇数位置后最后面的偶数位置，所以最多只需要遍历一般数组的长度即可，所以i<=len/2即可
}
}
}
2
3
4
5
6
7
8
9
10
11
# 3、第三种解法，但是并不是原地解法，至少比第一种要好一点，只保存偶数数据
运行时间：3ms 占用内存：484k odd奇数：even偶数
void reOrderArray(vector<int> &array) {
int len = array.size(),evenIndex = 0,oddIndex = 0;
if (len <= 1) return;
vector<int> temp(len/2+1,0);
for (int i = 0; i <len; ++i) {
if ( (array[i]&1) == 1) array[oddIndex++] = array[i];
else{
temp[evenIndex++] = array[i];//将偶数另外保存起来
}
}
for(int j = 0;j < evenIndex; ++j){
array[j + oddIndex] = temp[j];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
可以维护两个下表i，j。i从数组的头开始，j从数组的尾开始。使用两个while，i从前往后找到第一个偶数，j从后往前找到第一个奇数，然后这两个数交换。重复这个过程，直到i>=j。每次都能确保i前面的数都是奇数，j后面的数都是偶数。由于i始终增大，j始终减小，时间复杂度为On，此外也不需要开辟新的空间。