开发者社区> 陈国林> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

【37】调整数组顺序使奇数位于偶数前面

简介: 题目:输入一个整数数组,实现一个函数来调整该数组中数字的顺序使得所有奇数位于前面半部分,偶数位于后半部分。 分析: 1. 方案一:最朴素做法是枚举数组,发现一个奇数就把数字放到前面,然后移到后面的数字。
+关注继续查看


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


分析:

1. 方案一:最朴素做法是枚举数组,发现一个奇数就把数字放到前面,然后移到后面的数字。时间复杂度为O(n^2)

2. 方案二:最常用的的双指针法,设置两个指针p1,p2初始化指向数组的第一个数和数组的最后一个数。

     总的由以下四种情况

    (1)如果p1指向的数为奇数则p1向后移到一位,如果p2指向的数是偶数则p2向前移到一位。

    (2)如果p1指向的数为奇数则p1向后移到一位,如果p2指向的数为奇数则p2不变。

    (2)如果p1指向的数为偶数,p2指向的数是奇数;则此时把p1和p2两个值交换,p1向后移到一位p2向前移到一位

    (3)如果p1指向的数为偶数,p2指向的数是偶数;则p1不变p2往前移到一位。

     方案二,设置两个指针直到两个指针指向同一个位置结束,时间复杂度为O(n)

   

    举例:数组{2,0,1,3,4,5}

      (1)第一次数组如下所示,发现p1指向为偶数p2指向为奇数,则交换p1和p2的值  

 

       (2)第二次如图所示,发现p1指向的值为偶数则p1不变,p2指向为偶数,则p2向前移到一位

   

       (3)第三次如图所示 ,p1指向偶数,p2指向奇数则p1和p2值交换,p1向后移到一位,p2向前移到一位

      

        (4)第四次如图所示,发现p1和p2指向同一位置,说明以及把数组调整为奇数在前偶数在后

       


代码:

#include<iostream>
#include<algorithm>
using namespace std;

//把奇数放到偶数前面
void ReOrderArr(int *arrNum, int n){
    //数据不合法
	if(arrNum == NULL || n <= 0){
        return;
	} 
	int left = 0;
	int right = n-1;
	while(left < right){
        //left指向数为奇数 
        if(arrNum[left]&1 == 1){
           ++left;
		   //如果right指向的数为偶数
		   if(arrNum[right]&1 == 0){
   		      --right;
           } 
		}
        else{
	       //如果right指向的数为奇数 
		   if(arrNum[right]&1 == 1){
   		       swap(arrNum[left++], arrNum[right--]);
           } 
           else{
   		       --right;
           }
        }
	}
} 

int main(){     
    int arrNum[] = {2,0,1,3,4,5};
    ReOrderArr(arrNum, 6);
    //test
    for(int i = 0; i < 6; i++){
        cout<<arrNum[i]<<endl;
    }
    
    return 0;
}
/*
输出
5
3
1
0
4
2 
*/

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
12.调整数组顺序,使得奇数在前,偶数在后
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
0 0
【脚趾 Offer 21 】调整数组顺序使奇数位于偶数前面
【脚趾 Offer 21 】调整数组顺序使奇数位于偶数前面
0 0
调整数组顺序使奇数位于偶数前面(简单难度)
调整数组顺序使奇数位于偶数前面(简单难度)
0 0
AcWing 32. 调整数组顺序使奇数位于偶数前面
AcWing 32. 调整数组顺序使奇数位于偶数前面
0 0
每日一练(11):调整数组顺序使奇数位于偶数前面
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。
0 0
面试 6:调整数组顺序使奇数位于偶数前面
今天给大家带来的是 《剑指 Offer》习题:调整数组顺序使奇数位于偶数前面,纯 Java 实现希望大家多加思考。 面试题:输入一个整型数组,实现一个函数来调整该数组中的数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分,希望时间复杂度尽量小。
2174 0
[剑指offer] 调整数组顺序使奇数位于偶数前面
题目描述 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
850 0
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
如果不考虑奇数和奇数,偶数和偶数之间的相对位置不变。那么只需要两个指针分别指向数组的头和尾,依次比较。 1. 如果头指针指向的数组位置为奇数,那么就判断尾指针指向的数组位置的奇偶性。如果是奇数,则头指针后移一个位置,如果是偶数,则尾指针前移一个位置。
829 0
剑指offer(07)-调整数组顺序使奇数位于偶数前面【转】
来源:http://www.acmerblog.com/offer-6-2429/ 题目来自剑指offer系列 九度 1516 题目描述: 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
607 0
+关注
陈国林
曾任职于阿里巴巴,现就职于美图,专业搬砖100年~
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载