首页 > 代码库 > 【剑指Offer面试题】 九度OJ1516:调整数组顺序使奇数位于偶数前面

【剑指Offer面试题】 九度OJ1516:调整数组顺序使奇数位于偶数前面

题目链接地址:
http://ac.jobdu.com/problem.php?pid=1516

题目1516:调整数组顺序使奇数位于偶数前面

时间限制:1 秒内存限制:128 兆特殊判题:否提交:2858解决:924
题目描写叙述:
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得全部的奇数位于数组的前半部分,全部的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
输入:
每一个输入文件包括一组測试案例。
对于每一个測试案例。第一行输入一个n,代表该数组中数字的个数。
接下来的一行输入n个整数。

代表数组中的n个数。
输出:
相应每一个測试案例,
输入一行n个数字,代表调整后的数组。注意。数字和数字之间用一个空格隔开,最后一个数字后面没有空格。
例子输入:
5
1 2 3 4 5
例子输出:
1 3 5 2 4


思路分析:

剑指offer书上的问题比較简单。没有要求顺序不能变。方法(O(n)复杂度):

设定两个指向数组的指针,一个初始化数组第一个元素一个初始化最后一个元素,头指针向后扫描偶数。假设发现偶数,则让尾指针向前扫描,找出一个奇数。然后两者交换。

然后继续头指针向后扫描,直到尾指针在头指针的前面。结束。

但交换过程中把奇数之间、偶数之间的顺序给打乱了。不符合本题目的要求。
而九度题目进行了改进:
要求调整顺序。使得全部奇数在前面,全部偶数在后面,并且奇数之间的顺序不能变,偶数之间顺序不能变。即“调整顺序”和“相对位置不变”。
方法:
  

  1. 一个数组扫描两次。先后记录奇数和偶数,再将数组先后写回原数组。时间和空间复杂度均为O(n)。
  2. 构建两个数组。记录奇数和偶数。再将数组写回原数组,时间和空间复杂度均为O(n)。

  3. 构建两个单链表,一个存放奇数。一个存放偶数;再将奇偶数写回原数组。时间和空间复杂度均为O(n)。

代码:

/********************************* 
【剑指Offer面试题】 九度OJ1516:调整数组顺序使奇数位于偶数前面
Author:牧之丶  Date:2015年
Email:bzhou84@163.com 
**********************************/ 
#include<stdio.h>
#include<stdlib.h>  
#include<string>
#include <math.h>
#include<stack>
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> odd, even;
    int n, i, num;
    while(scanf("%d", &n)!= EOF){
        odd.clear();
        even.clear();
        for(i = 0; i < n; ++i){
            scanf("%d", &num);
            num & 1 ? odd.push_back(num) : even.push_back(num);
        }
        for(i = 0; i < even.size(); ++i){
            odd.push_back(even[i]);
        }
        printf("%d", odd[0]);
        for(i = 1; i < odd.size(); ++i){
            printf(" %d", odd[i]);
        }
        printf("\n");
    }
    return 0;
}
/**************************************************************
    Problem: 1516
    Language: C++
    Result: Accepted
    Time:80 ms
    Memory:2552 kb
****************************************************************/

总结:

  • 善用两个指针
  • 善于开辟数组辅助
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

【剑指Offer面试题】 九度OJ1516:调整数组顺序使奇数位于偶数前面