设为首页 加入收藏

TOP

剑指offer:调整数组顺序使奇数位于偶数前面(一)
2019-03-01 20:08:16 】 浏览:159
Tags:剑指 offer 整数 顺序 奇数位于 偶数 前面

题目

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

分析

事实上,这个题比较简单,很多种方式都可以实现,但是其时间复杂度或空间复杂度不尽相同。

解法一

书中作者提到一种初始的做法是,从头扫描整个数组,如果遇到偶数,则拿出这个数,并且把整个数组的数据都向前挪动一位,再把拿出的数放到末尾。每碰到一个偶数就需要移动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++;

            /*交换后继续*/
          
编程开发网
首页 上一页 1 2 3 4 下一页 尾页 1/4/4
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇1-1 编程总结:查找整数 下一篇C语言中关于逗号运算符的理解

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }