首页 > 试题广场 >

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

[编程题]调整数组顺序使奇数位于偶数前面
  • 热度指数：887021 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
算法知识视频讲解
添加回答
推荐
nailperry头像 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头像 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头像 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头像 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头像 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头像 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头像 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头像 北风呼啸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头像 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头像 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头像 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头像 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)
提交观点

问题信息

数组
来自：编程题练习卷
难度：
2674条回答 302881浏览

热门推荐

通过挑战的用户

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号