首页 > 试题广场 >

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

[编程题]调整数组顺序使奇数位于偶数前面

热度指数：887019 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

算法知识视频讲解

查看答案及解析

推荐

nailperry

    /**
     * 1.要想保证原有次序，则只能顺次移动或相邻交换。
     * 2.i从左向右遍历，找到第一个偶数。
     * 3.j从i+1开始向后找，直到找到第一个奇数。
     * 4.将[i,...,j-1]的元素整体后移一位，最后将找到的奇数放入i位置，然后i++。
     * 5.終止條件：j向後遍歷查找失敗。
     */
    public void reOrderArray2(int [] a) {
    	if(a==null||a.length==0)
    		return;
        int i = 0,j;
        while(i<a.length){
        	while(i<a.length&&!isEven(a[i]))
        		i++;
        	j = i+1;
        	while(j<a.length&&isEven(a[j]))
        		j++;
        	if(j<a.length){
        		int tmp = a[j];
        		for (int j2 = j-1; j2 >=i; j2--) {
					a[j2+1] = a[j2];
				}
        		a[i++] = tmp;
        	}else{// 查找失敗
        		break;
        	}
        }
    }
    boolean isEven(int n){
    	if(n%2==0)
    		return true;
    	return false;
    }

编辑于 2015-08-18 23:19:51 回复(102)

Java

OutOfBoundsException

从题目得出的信息：

相对位置不变--->保持稳定性；奇数位于前面，偶数位于后面 --->存在判断，挪动元素位置；

这些都和内部排序算法相似，考虑到具有稳定性的排序算法不多，例如插入排序，归并排序等；这里采用插入排序的思想实现。

public class Solution {
    public void reOrderArray(int [] array) {
        //相对位置不变，稳定性
        //插入排序的思想
        int m = array.length;
        int k = 0;//记录已经摆好位置的奇数的个数
        for (int i = 0; i < m; i++) {
            if (array[i] % 2 == 1) {
                int j = i;
                while (j > k) {//j >= k+1
                    int tmp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = tmp;
                    j--;
                }
                k++;
            }
        }
    }
}

编辑于 2017-10-31 21:17:56 回复(22)

walter52

//两个思路吧，第一个思路：类似冒泡算法，前偶后奇数就交换：
class Solution {
public:
	void reOrderArray(vector<int> &array) {

		
		for (int i = 0; i < array.size();i++)
		{
			for (int j = array.size() - 1; j>i;j--)
			{
				if (array[j] % 2 == 1 && array[j - 1]%2 == 0) //前偶后奇交换
				{
					swap(array[j], array[j-1]);
				}
			}
		}
	}
};

//第二个思路：再创建一个数组 
class Solution{
public:
	void reOrderArray(vector<int> &array) {

		vector<int> array_temp;
		vector<int>::iterator ib1, ie1;
		ib1 = array.begin();


		for (; ib1 != array.end();){            //遇见偶数，就保存到新数组，同时从原数组中删除 
			if (*ib1 % 2 == 0) {
				array_temp.push_back(*ib1);
				ib1 = array.erase(ib1);
			}
			else{
				ib1++;
			}

		}
		vector<int>::iterator ib2, ie2;
		ib2 = array_temp.begin();
		ie2 = array_temp.end();

		for (; ib2 != ie2; ib2++)             //将新数组的数添加到老数组
		{
			array.push_back(*ib2);
		}
	}
};

编辑于 2015-08-19 20:58:42 回复(83)

C/C++

noobfox

用的STL　stable_partition 这个函数

函数功能是将数组中　isOk为真的放在数组前，假的放在数组后，和题意相符

bool isOk(int n){  return ((n & 1) == 1);　//奇数返回真 }

class Solution{
	void reOrderArray(vector<int> &array){
		stable_partition(array.begin(),array.end(),isOk);
	}
};

下次贴上这个stable_partition实现～

发表于 2016-06-27 00:30:42 回复(20)

Python

华科平凡

python4行解法:

def reOrderArray(self, array):
        # write code here
        odd,even=[],[]
        for i in array:
            odd.append(i) if i%2==1 else even.append(i)
        return odd+even

一行解法，使用lambda表达式

return sorted(array,key=lambda c:c%2,reverse=True)

编辑于 2017-09-11 09:07:23 回复(44)

令狐冲_钟跃民

时间复杂度为O（n），空间复杂度为O（n）的算法
/*
整体思路：
首先统计奇数的个数
然后新建一个等长数组，设置两个指针，奇数指针从0开始，偶数指针从奇数个数的末尾开始 遍历，填数
*/
public class Solution {
    public void reOrderArray(int [] array) {
        if(array.length==0||array.length==1) return;
        int oddCount=0,oddBegin=0;
        int[] newArray=new int[array.length];
        for(int i=0;i<array.length;i++){
            if((array[i]&1)==1) oddCount++;
        }
        for(int i=0;i<array.length;i++){
            if((array[i]&1)==1) newArray[oddBegin++]=array[i];
            else newArray[oddCount++]=array[i];
        }
        for(int i=0;i<array.length;i++){
            array[i]=newArray[i];
        }
    }
}

发表于 2016-05-09 11:48:39 回复(40)

Java

我买桂花和酒

新开数组空间换时间的解法,

a.遍历数组,如果是奇数从头部放入到原数组中,并记录指针

b.如果是偶数,放入到新数组中,并记录指针

c.将新数组的元素安顺序,从最后一个奇数后边插入到原数组中

public class Solution {
    public void reOrderArray(int [] array) {
        if (array != null) {
            int[] even = new int[array.length];
            int indexOdd = 0;
            int indexEven = 0;
            for (int num : array) {
                if ((num & 1) == 1) {
                    array[indexOdd++] = num;
                } else {
                    even[indexEven++] = num;
                }
            }

            for (int i = 0; i < indexEven; i++) {
                array[indexOdd + i] = even[i];
            }
        }
    }
}

编辑于 2018-04-13 14:14:50 回复(1)

zgljl2012

类似插入排序，当前数是奇数，就往前找，遇到偶数就往它前面插

class Solution {
public:
 void reOrderArray(vector<int> &array) {
  for (int i = 1; i < array.size(); i++){
   int tmp = array[i];
   if (tmp % 2 == 1){
    for (int j = i; j > 0; j--){
     if (array[j - 1] % 2 == 0){
      int t = array[j];
      array[j] = array[j - 1];
      array[j - 1] = t;
     }
    }
   }
  }
 }
};

发表于 2015-05-18 16:46:17 回复(18)

菰獨ゞ漩嵂ヤ

只需要一次遍历，实质是舍弃空间，缩减时间：重新定义一个相同大小数组，遍历第一个数组，同时从两端进行判断，从左边的只负责判断奇数，遇到就放入新数组（正向放入）；从右边的只负责判断偶数，遇到就放入新数组（后从向前放），一遍循环结束，新数组就是按照要求排序了的

public void reOrderArray(int [] array) {
        int [] tmp = new int[array.length];
        int j=0;
        int o=array.length - 1;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 != 0) {
                tmp[j++] = array[i];
            }
            if (array[array.length - i - 1] % 2 == 0) {
                tmp[o--] = array[array.length - i - 1];
            }
        }
        for (int i = 0; i < tmp.length; i++) {
            array[i] = tmp[i];
        }
    }

发表于 2017-08-14 17:33:11 回复(4)

码农小菜

        if(array==null){
            return;
        }
        //原书中的方法 类似于快排
        /*int i=0;
        int j=array.length-1;
        while(i<j){
            while(i<j&&array[i]%2==1){
                i++;
            }
            while(i<j&&array[j]%2==0){
                j--;
            }
            int temp=array[j];
            array[j]=array[i];
            array[i]=temp;
        }*/
        //由于要保证稳定即证奇数和奇数，偶数和偶数之间的相对位置不变 使用插入排序思想
        for(int i=0;i<array.length;i++){
            //int temp=array[i];
            if(array[i]%2==1){
                int temp=array[i];
                int j=i-1;
                while(j>=0&&array[j]%2==0){
                    array[j+1]=array[j];
                    j--;
                }
                array[j+1]=temp;
            }            
        }

发表于 2015-04-21 16:33:54 回复(7)

习惯不曾习惯












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

采用冒泡排序的思想，如果采用另开辟一个数组的话，相当于拿空间换时间。

发表于 2017-04-22 14:48:16 回复(1)

worsun

这道题考察的排序。
这题这一看，分成两部本，太开心了，原来是快排的变种，于是写了程序，后来结果大家知道了，肯定不满足相对位置不变这个条件。因为快排本身就是不稳定的算法，稳定高效的排序算法常用的只有归并了，堆排也是不稳定的。所以，用归并排序的思想解决较合适。时间复杂度低。代码如下：

public class Solution {
    public void reOrderArray(int [] array) {
        //注释的部分使用快速排序的算法，很明显快速排序是不稳定的，这里需要用归并排序
        /*
        if(array.length == 0){
            return;
        }
        int high = array.length - 1;
        int low = 0;
        while(low < high){
            while(low < high && array[low] % 2 == 1){
                low ++;
            }
            while(low < high && array[high] % 2 == 0){
                high --;
            }
            int temp = array[low];
            array[low] = array[high];
            array[high] = temp;
        }*/

        //用用归并排序的思想，因为归并排序是稳定的
        int length = array.length;
        if(length == 0){
            return;
        }
        int[] des = new int[length];
        MergeMethod(array, des, 0,length - 1);
    }
    public void MergeMethod(int[] array, int [] des, int start, int end){
        if(start < end){
            int mid = (start + end) / 2;
            MergeMethod(array, des, start, mid);
            MergeMethod(array, des, mid + 1, end);
            Merge(array, des, start, mid, end);
        }
    }

    public void Merge(int[] array, int[] des, int start, int mid, int end){
        int i = start;
        int j = mid + 1;
        int k = start;
        while(i <= mid && array[i] % 2 == 1){
            des[k++] = array[i++];
        }
        while(j <= end && array[j] % 2 == 1){
            des[k++] = array[j++];
        }
        while(i <= mid){
            des[k++] = array[i++];
        }
        while(j <= end){
            des[k++] = array[j++];
        }

        for(int m = start; m <= end; m++){
            array[m] = des[m];
        }
    }
}

发表于 2016-03-18 15:47:24 回复(13)

乌邦图

时间复杂度为O(n)；空间复杂度为O(1)，遍历一遍即可

void reOrderArray(vector<int> &array) {
        int len = array.size();
        vector<int> :: iterator it = array.begin();
        for(int i=0;i<len;i++)
            {
            if(*it%2==0){
                int tmp = *it;
                array.erase(it);
                array.push_back(tmp);
            }
            else
                it++;
        }
    }

发表于 2017-10-18 18:30:15 回复(7)

anhoulin

首先想到的就是类似于插入排序，而且我感觉插入排序还是比较好的，毕竟不用借助其他的数据结构，

所以空间复杂度为O（1），时间复杂度为O（N^2）

public void reOrderArray(int [] array) {
        for(int i=1;i<array.length;i++){
            int target = array[i];
            if(array[i] % 2 == 1){
                int j = i;
                while(j >= 1 && array[j-1] % 2 == 0){
                    array[j] = array[j-1];
                    j--;
                }
                array[j] = target;
            }
        }
    }

发表于 2016-08-09 16:52:52 回复(5)

北风呼啸ZJU

队列中添加两个指针a,b。其中a是下一个奇数位所要放置的位置，b指针用来遍历队列。

判断b指向元素是否为奇数，如果不是b后移一位继续判断是否为奇数，如果是奇数，则将a与b之间的元素后移一位，并将b原来的值插入a处，同时将a指针后移一位。

代码如下：

void reOrderArray(vector<int> &array) {
 vector<int>::iterator currentIter = array.begin();
 for (vector<int>::iterator it = array.begin(); it != array.end(); it++)
 {
  if (*it % 2 == 1)
  {
   if (it != currentIter)
   {
    int nTemp = *it;
    for (vector<int>::iterator it1 = it; it1 != currentIter; it1--)
    {
     *it1 = *(it1 - 1);
    }
    *currentIter = nTemp;
   }
   currentIter++;
  }
 }
}

编辑于 2015-09-24 11:22:03 回复(3)

Ethan_4


class Solution:
    def reOrderArray(self, array):
        array.sort(key=lambda item:item%2,reverse=True)
        return array

编辑于 2016-09-03 23:40:09 回复(2)

Python

啥也没有

python真好用

x = filter(lambda x : x%2 != 0,array)
y = filter(lambda x : x%2 == 0,array)
return x+y

发表于 2017-04-10 18:02:19 回复(9)

KingMJ

class Solution:
    def reOrderArray(self, array):
        # write code here
        a = []#保存奇数
        b = []#保存偶数
        for i in array:
            if (i%2):
                a.append(i)
            else:
                b.append(i)
        return a+b

发表于 2016-09-03 17:07:16 回复(8)

Batman007

其实就是快排的变种，虽然快排是不稳定的，但是可以稍微改进一下，下面是根据算法导论的快排改编的
class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int size = array.size();
        if(size == 0 || size == 1) return;
        int p = -1;
        int q = 0;
        while(q < size) {
            if ((array[q] & 1) != 0) {
                p++;
                int i = q;
                int temp = array[i];
                while(i > p) {
                    array[i] = array[i-1];
                    i--;
                }
                array[p] = temp;
            }
            q++;
        }
    }
};

发表于 2016-04-04 13:25:13 回复(10)

Java

吴大城

主要就是需要考虑到代码完整性，问题本身比较简单。我的解题思路是：新建两个临时数组，一个按顺序存放奇数，一个按照顺序存放偶数。然后将奇数和偶数两个数组依次放入原数组。代码如下：

//时间17ms，内存9288k
public class Solution {
    public void reOrderArray(int [] array) {
        int [] odd = new int[array.length];//奇数数组
        int [] even = new int[array.length];//偶数数组
        int odd_number = 0;//奇数个数
        int even_number = 0;//偶数个数
        
        for(int i = 0;i<array.length;i++){//遍历原数组
            switch(array[i]%2){
                case 1://奇数
                    odd[odd_number] = array[i];
                    odd_number ++;
                    break;
                default://偶数
                    even[even_number] = array[i];
                    even_number++;
                    break;
            }
        }
        for(int i =0,x=0;i<array.length;i++){
            if(i<odd_number){
                array[i] = odd[i];
            }else{
                array[i] = even[x];
                x++;
            }
        }
    }
}

发表于 2019-10-20 10:05:33 回复(0)

Java

NotOfferException

完全按照简单插入排序思想：

public class Solution {
public void reOrderArray(int [] array) {
for(int i = 0; i < array.length; i++){
if(array[i] % 2 == 1){
int temp = array[i];
int j = i;
while(j>0 && array[j-1]%2 == 0){
array[j] = array[j-1];
j--;
}
if(i != j)
array[j] = temp;
}
}
}
}

发表于 2019-04-11 20:10:59 回复(3)