首页 > 试题广场 > 调整数组顺序使奇数位于偶数前面
[编程题]调整数组顺序使奇数位于偶数前面
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

1689个回答

添加回答
推荐
 /** * 1.要想保证原有
   查看全部
编辑于 2015-08-18 23:19:51 回复(61)
//两个思路吧,第一个思路:类似冒泡算法,前偶后奇数就交换:
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 回复(57)
用的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 回复(14)
时间复杂度为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 回复(32)

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 回复(17)
// 不能学排序算法学傻了吧,这题不至于上各种排序算法吧还
/*新建一个数组先把原数组中的奇数push进去再把偶数push进去,然后用新数组数据覆盖原数组即可
复杂度O(n)
*/
class Solution {
public:
    void reOrderArray(vector<int> &array) {
        vector<int> res;
        for(int i = 0; i < array.size(); i++)
        {
            if(array[i] % 2 == 1)
                res.push_back(array[i]);
        }
        for(int i = 0; i < array.size(); i++)
        {
            if(array[i] % 2 == 0)
                res.push_back(array[i]);
        }
        //array.swap(res);
        array = res;
       
    }
};

编辑于 2016-07-26 16:33:42 回复(32)
从题目得出的信息:
相对位置不变--->保持稳定性;奇数位于前面,偶数位于后面 --->存在判断,挪动元素位置;
这些都和内部排序算法相似,考虑到具有稳定性的排序算法不多,例如插入排序,归并排序等;这里采用插入排序的思想实现。
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 回复(3)

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

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

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)
        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 回复(5)











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)
首先想到的就是类似于插入排序,而且我感觉插入排序还是比较好的,毕竟不用借助其他的数据结构,
所以空间复杂度为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 回复(2)
新开数组空间换时间的解法,
    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 回复(0)
时间复杂度为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 回复(2)

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

编辑于 2016-09-03 23:40:09 回复(1)
其实就是快排的变种,虽然快排是不稳定的,但是可以稍微改进一下,下面是根据算法导论的快排改编的
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 回复(8)
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 回复(3)
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 回复(5)
ArrayList<Integer> a = new ArrayList<>(); ArrayList<Integer> b = new ArrayList<>(); int[] result = new int[array.length]; for (int i = 0; i < array.length; i++) { if (array[i] % 2 == 0) {
        b.add(array[i]);  } else {
        a.add(array[i]);  }
} ArrayList<Integer> list = new ArrayList<>(); list.addAll(a); list.addAll(b);  for (int j = 0; j < array.length; j++) { if (j < a.size()) {
        array[j] = a.get(j);  } else {
        array[j] = b.get(j - a.size());  }
}
发表于 2016-03-25 19:38:31 回复(4)
public class Solution {
    public void reOrderArray(int [] array) {
        int[] odd = new int[array.length];
        int[] even = new int[array.length];
        int evenCount=0;
        int oddCount=0;
        for(int i=0;i<array.length;i++){
            if(array[i]%2==0){
                even[evenCount] = array[i];
                evenCount++;
            }else{
                odd[oddCount] = array[i];
                oddCount++;
            }
        }
		for(int i=0;i<oddCount;i++){
            array[i] = odd[i];
        }
        for(int i=0;i<evenCount;i++){
            array[i+oddCount] = even[i];
        }
        
    }
}
来个时间复杂度最低的

发表于 2016-02-29 16:17:13 回复(4)
队列中添加两个指针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 回复(2)

问题信息

难度:
1689条回答 138976浏览

热门推荐

通过挑战的用户

查看代码

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

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

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号