专栏首页全部文章Day13 :调整数组顺序使奇数位于偶数前面

Day13 :调整数组顺序使奇数位于偶数前面

剑指Offer_编程题——调整数组顺序使奇数位于偶数前面

题目描述:

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间相对位置不变。

具体要求:

时间限制: C/C++ 1秒,其他语言2秒 空间限制: C/C++32M,其他语言64M

具体思路:

思路一:   根据题意可知,我们不仅要让奇数在偶数的前面,还要考虑奇数和偶数原来的相对位置不变。因此我们首先要寻找第一个奇数,并将其放在0号位置。然后将第一个奇数之前的元素全部往后移一位。依次再第一个奇数之后的元素中寻找奇数,并做移动操作,就可以保证原来的相对顺序。 接下来我们用java实现

public class Solution{
	public static void reOrderArray(int [] array){
		int j = 0;
		int m = 0;
		for(int i = 0; i < array.length; i++){
			if(array[i] % 2 == 1){
				int temp = array[i];
				int ti = i;
				for(; ti > 0; ti --){
					array[ti] = array[ti - 1]; 
				}
				   array[0] = temp;
				   j = i;
				   break;
			}
		}
		for(++j; j < array.length; j++){
			if(array[j] % 2 == 1){
				int temp = array[j];
				int tj = j;
				for(; tj > m; tj--){
					array[tj] = array[tj - 1];
				}
					array[++m] = temp;
			}
		}
	}
}

代码效果图如图所示:

  在编译器中加入main()函数,进行代码可行性测试,具体测试代码实现入下:

public static void main(String[] args){
	int []array = {2, 4, 6, 1, 3, 5, 7};
	reOrderArray(array);
	for(int i = 0; i < array.length; i++){
		System.out.pritnln(array[i] + " ");
	}
}

  代码测试通过如下图所示:

思路二:   还可以新建两个数组,分别存放奇数和偶数。然后再进行合并。具体用python来进行实现。

class Solution:
    def reOrderArray(self, array):
        # write code here
        a = []
        b = []
        for i in array:
            if i % 2 == 1:
                a.append(i)
            else:
                b.append(i)
        a.extend(b)
        return a

代码效果图如图所示:

拓展:   如果去掉并保证奇数和奇数,偶数和偶数之间的相对位置不变。还有另一种做法。我们可以用java将其实现,方法比较简单。只需要两个指针分别指向数组的头和尾,依次比较。具体实现步骤如下: 1、如果头指针指向数组位置为奇数,那么就判断尾指针指向的数组位置的奇偶性,如果是奇数,则头指针指向的数组位置为偶数,则尾指针前移一个位置。 2、如果头指针指向的数组位置为偶数,那么就判断尾指针指向的数组位置的奇偶性。如果是奇数,则交换头尾指针指向的数组元素,如果是偶数,则尾指针前移一个位置。 具体用java实现如下:

public class Solution{
	public static void main(String[] args){
		int []array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
		reOrderArray(array);
		for(int i = 0; i < array.length; i++){
			System.out.println(array[i] + " ");
		}
	}
public static void reOrderArray(int [] array){
	int i = 0;
	int j = array.length - 1;
	while(i < j){
		if (array[i] % 2 == 1){
			if(array[j] % 2 == 1){
				i++;
			}else{
				j --;
			}
		}else{
			if(array[j] % 2 ==1){
				int temp = array[i];
				array[i] = array[j];
				array[j] = temp;
			}else{
				j--;
				}
			}
		}
	}
}

代码测试如图所示:

总结

  本道题主要通过一个数组考察奇偶数的位置,并且特意强调调整位置后,要保证原来的相对位置。这就增加了一定的难度,这就需要寻找第一个奇数并放入数组的开头,然后继续将数组往后移动。然后,如果去掉这个“保持位置不变”的情况,则变得相对简单,只需要让两个指分别指向数组的头和尾,依次比较即可。总之,继续加油,争取早日找到工作,Good Luck!!!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Day42:和为S的两个数字

    思路二: 1.定义两个指针,第一个指向第一个元素,第二个指向最后一个元素; 2.先拿第一个元素和最后一个元素相加,与要求的数字进行比较;   1)如果...

    stefan666
  • Day 6:旋转数组的最小数字

    思路1:二分查找(折半查找)+递归算法 根据题意可知,数组是非递减的,是有序的,最适合的就是二分查找了 当array[mid]>array[left]时,最...

    stefan666
  • Day30:连续子数组的最大和

    背景知识介绍   在做题前,首先给大家介绍一种非常典型的算法——动态规划算法。在维基百科中,动态规划算法是这样解释的:动态规划(英语:Dynamic prog...

    stefan666
  • 《剑指offer》第12天:旋转数组的最小数字

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。例如数组 {3,4,5,1,2} 为...

    程序员小浩
  • python--几种快速排序的实现以及运行时间比较

    快速排序的基本思想:首先选定一个数组中的一个初始值,将数组中比该值小的放在左边,比该值大的放在右边,然后分别对左边的数组进行如上的操作,对右边的数组进行如上的操...

    绝命生
  • PHP实现冒泡排序

    冒泡排序属于交换排序,是一种稳定排序,平均时间复杂度为 O(n^2),最好情况时间复杂度为O(n),最坏情况时间复杂度为O(n^2)。 <?php /...

    Clive
  • 【Python】冒泡排序

    在本科学C++的时候,一个最有意思的程序就是冒泡啦,还记得那可是让无数人摸不清头脑,抓狂到喷血的程序,的确很容易一时转不过来,不过一想通的话马上就觉得代码真的是...

    企鹅号小编
  • 常用七种排序的python实现

    算法复杂度分为时间复杂度和空间复杂度。其中, 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。

    用户1432189
  • 跟我学习php数组常用函数-下篇

    如果是递归的,结果:array('hobby' => array('a' => 'ping-pong', 'b' => 'basketball'));

    _simple
  • 跟我学习php数组常用函数-上篇

    _simple

扫码关注云+社区

领取腾讯云代金券