内容简介:输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。事实上,这个题比较简单,很多种方式都可以实现,但是其时间复杂度或空间复杂度不尽相同。书中作者提到一种初始的做法是,从头扫描整个数组,如果遇到偶数,则拿出这个数,并且把整个数组的数据都向前挪动一位,再把拿出的数放到末尾。每碰到一个偶数就需要移动O(N)次,这样总的
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。
分析
事实上,这个题比较简单,很多种方式都可以实现,但是其时间复杂度或空间复杂度不尽相同。
解法一
书中作者提到一种初始的做法是,从头扫描整个数组,如果遇到偶数,则拿出这个数,并且把整个数组的数据都向前挪动一位,再把拿出的数放到末尾。每碰到一个偶数就需要移动O(N)次,这样总的 时间复杂度为O(n^2),空间复杂度为O(1) 。
这种方式很简单,如果已经很清楚是怎么回事,可以跳过例子说明,继续阅读下一个解法。但是 可以尝试自己写一下代码,发现有些细节部分并不是那么容易写出来 。
举个例子,假设有数据1,2,3,4,5,6:
从左往右扫描,找到第一个偶数2,并临时保存:
1 | 2 | 3 | 4 | 5 | 6 |
↑ | |||||
取出 |
将2后面的所有数往前移动一个位置,并将2放到最后一个位置:
1 | 3 | 4 | 5 | 6 | 2 |
↑ | 移动后 |
继续扫描 当前位置 ,发现3为奇数,继续,发现4为偶数,将从3之后位置的数开始,到倒数第二个位置,所有数往前移动一个位置,并将4放到最后:
1 | 3 | 5 | 6 | 4 | 2 |
↑ | 移动后 |
继续扫描当前位置数5,6,至此,偶数有2两个,当前指向位置为,所在下标为4,总数 - 位置 <= 偶数 ,结束。
1 | 3 | 5 | 6 | 4 | 2 |
↑ |
根据该思路,C语言代码实现如下:
//reorder.c #include<stdio.h> #include<stdlib.h> #include<time.h> #include<string.h> void reorder(int arr[],int len) { if(NULL == arr || 0 == len) return; /*统计偶数数量,减少移动次数*/ int evenNum = 0; int loop = 0; int temp; int inLoop = 0; while(loop < len) { /*如果是偶数,则需要开始移动*/ temp = arr[loop]; /*如果已经达到了*/ if(0 == (temp & 1) && (len - loop > evenNum)) { /*从当前位置开始移动,直到遇到剩下的数量是偶数的个数*/ for(inLoop = loop + 1;inLoop < len - evenNum;inLoop++) { arr[inLoop-1] = arr[inLoop]; } /*把空出来的位填充上*/ arr[len - evenNum - 1] = temp; evenNum++; /*交换后继续*/ continue; } /*继续循环下一个*/ else { loop++; } } } void printArray(int A[],int n) { if(n > 100) { printf("too much,will not print\n"); return; } int i = 0; while(i < n) { printf("%d ",A[i]); i++; } printf("\n"); } int main(int argc,char *argv[]) { if(argc < 2) { printf("usage:reorder num\n"); return -1; } int len = atoi(argv[1]); printf("reorder for %d numbers\n",len); /*随机产生输入数量的数据*/ int *A = malloc(sizeof(int)*len); int i = 0; srand(time(NULL)); while(i < len) { A[i] = rand()%100; i++; } printf("before reorder:"); printArray(A,len); /*对数据进行排序*/ reorder(A,len); printf("after reorder:"); printArray(A,len); free(A); return 0; }
解法二
很多人其实最先想到的解法可能是,创建一个新的数组,从头扫描,遇到偶数放后边,遇到奇数放前边。扫描结束后,再将数组内容拷贝到原数组,这样整个 时间复杂度为(n),而空间复杂度也为O(n) ,这样的方法实现简单,也不容易出错。C语言代码实现如下(省略了main函数以及printArr函数):
//reorder1.c void reorder(int arr[],int len) { if(NULL == arr || 0 == len) return; /*记录奇偶的数量*/ int oddNum = 0; int evenNum = 0; int loop = 0; /*创建一个新的数组*/ int *temp = malloc(len * sizeof(int)); if(NULL == temp) { printf("malloc memory failed\n"); return; } /*拷贝数组,并遍历*/ memcpy(temp,arr,sizeof(int)*len); for(;loop < len;loop++) { /*偶数放到数组末尾*/ if(0 == (temp[loop] & 1)) { arr[len-1-evenNum] = temp[loop]; evenNum++; } /*奇数放到数组末尾*/ else { arr[oddNum] = temp[loop]; oddNum++; } } free(temp); }
解法三
还记得我们之前介绍过的《快速 排序 优化详解》吗?快速排序中,有一个分区操作,是将整个数组大于基准的部分,放右边,而小于基准的部分放右边,即根据基准,将数组一分为二。其实在这里,同样可以参考这个思路,只不过跟基准比大小,变成了判断是奇还是偶。
这里简单描述一下该思路,更多细节可以参考《快速排序优化详解》中如何将元素移动到基准两侧一节:
- 定义下标i和j,分别从开头和结尾开始扫描
- 当i遇到偶数时,停止扫描
- 当j遇到奇数时,停止扫描
- 此时交换i和j位置的值
- 继续前面的操作,直到i和j交错或相等
举个例子,假设有数据1,2,3,4,5,6,7,8:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
↑ | ↑ | ||||||
i | j |
i和j继续扫描,i遇到2停止,j遇到5停止,交换两处的值:
1 | 7 | 3 | 4 | 5 | 6 | 2 | 8 |
↑ | ↑ | ||||||
i | j |
i和j继续扫描,i遇到4停止,j遇到5停止,交换两处的值:
1 | 7 | 3 | 5 | 4 | 6 | 2 | 8 |
↑ | ↑ | ||||||
i | j |
继续扫描,此时,i和j交错,扫描结束:
1 | 7 | 3 | 5 | 4 | 6 | 2 | 8 |
↑ | ↑ | ||||||
j | i |
基于该思路的算法 时间复杂度为O(n),空间复杂度为O(1) ,C语言代码实现如下(省略了main函数以及printArr函数):
//reorder2.c void reorder(int arr[],int len) { if(NULL == arr || 0 == len) return; int i = 0; int j = len - 1; int temp; for(;;) { /*i j分别向右和向左移动,i遇到偶数停止,j遇到奇数停止?*/ while(1 == (arr[i] & 1)) { i++; } while(0 == (arr[j] & 1)) { j--; } if(i < j) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } /*交错时停止*/ else { break; } } }
运行效率比较
编译后,对一百万数据进行操作,运行时间结果如下。
解法一:
$ time ./reorder 1000000
并没有耐心等到结果出来。
解法二:
$ time ./reorder1 1000000 reorder for 100000000 numbers before reorder:too much,will not print after reorder:too much,will not print real 0m2.425s user 0m2.141s sys 0m0.284s
对1亿数据进行操作,耗时很短,只是内存占用较多。
解法三:
$ time ./reorder2 1000000 reorder for 100000000 numbers before reorder:too much,will not print after reorder:too much,will not print real 0m2.146s user 0m2.018s sys 0m0.128s
耗时很短,内存占用少。
扩展
在本题中,只是对整数是奇还是偶进行分开,那么如果是别的条件呢?例如是否为素数,是否为正数等等。我们可以让调用者传入一个条件函数,让它决定到底是放在后半部分,还是前半部分。这是不是很向库函数qsort需要传入一个比较函数的做法?这部分内容可以参考《函数指针》,根据这个思路,我们修改解法三的代码:
//reorder3.c /*定义函数指针类型*/ typedef int(*CheckFun)(int); int isMatch(int num) { if(0 == (num & 1)) return 1; else return 0; } void reorder(int arr[],int len,CheckFun isMatch) { if(NULL == arr || 0 == len || NULL == isMatch) return; int i = 0; int j = len - 1; int temp; for(;;) { /*i j分别向右和向左移动,i遇到偶数停止,j遇到奇数停止?*/ while(!(*isMatch)(arr[i])) { i++; } while((*isMatch)(arr[j])) { j--; } if(i < j) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } /*交错时停止*/ else { break; } } }
这个时候通过传入函数指针,可以对任意条件进行处理了。
总结
我们发现,一些基本算法的思想,通常可以用到其他问题上,而不同的思路,带来的效率可能天差地别。
以上所述就是小编给大家介绍的《剑指offer:调整数组顺序使奇数位于偶数前面》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- golang两个协成交替打印1-100的奇数偶数
- C语言实现将一个数组中的奇数和偶数分开放在一起
- FreeCodeCamp 中级算法题 - 斐波那契数列奇数项求和
- 偶数科技构建新一代数据仓库,与AI应用场景更契合
- 专访偶数科技常雷:从商业走向开源,Apache HAWQ 适应得很好
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Linux Device Drivers
Jonathan Corbet、Alessandro Rubini、Greg Kroah-Hartman / O'Reilly Media / 2005-2-17 / USD 39.95
Device drivers literally drive everything you're interested in--disks, monitors, keyboards, modems--everything outside the computer chip and memory. And writing device drivers is one of the few areas ......一起来看看 《Linux Device Drivers》 这本书的介绍吧!
HTML 编码/解码
HTML 编码/解码
HEX HSV 转换工具
HEX HSV 互换工具