剑指offer:调整数组顺序使奇数位于偶数前面

栏目: C · 发布时间: 5年前

内容简介:输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。事实上,这个题比较简单,很多种方式都可以实现,但是其时间复杂度或空间复杂度不尽相同。书中作者提到一种初始的做法是,从头扫描整个数组,如果遇到偶数,则拿出这个数,并且把整个数组的数据都向前挪动一位,再把拿出的数放到末尾。每碰到一个偶数就需要移动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:调整数组顺序使奇数位于偶数前面》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Linux Device Drivers

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 编码/解码

HTML 编码/解码

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具