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

1832个回答

添加回答
 秒速快三代理网址 www.kxiwk11.cn public class Solution {
? ? public void reOrderArray(int [] array) {
? ? ? ? int len = array.length;
? ? ? ? int[] cop1 = new int[len];
? ? ? ? int[] cop2 = new int[len];
? ? ? ? int cntj = 0;
? ? ? ? int cnto = 0;
? ? ? ? for (int i = 0; i < len; i++) {
? ? ? ? ? ? if (array[i] % 2 == 1)
? ? ? ? ? ? ? ? cop1[cntj++] = array[i];
? ? ? ? ? ? else
? ? ? ? ? ? ? ? cop2[cnto++] = array[i];
? ? ? ? }
? ? ? ? for (int i = 0; i < cntj; i++)
? ? ? ? ? ? array[i] = cop1[i];
? ? ? ? for (int i = 0; i < cnto; i++)
? ? ? ? ? ? array[i+cntj] = cop2[i];
? ? }
}

发表于 2019-03-15 14:05:04 回复(0)
更多回答
推荐
 /** * 1.要想保证原有
   查看全部
编辑于 2015-08-18 23:19:51 回复(71)
//两个思路吧,第一个思路:类似冒泡算法,前偶后奇数就交换:
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 回复(60)
用的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 回复(16)
时间复杂度为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 回复(35)

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 回复(24)
// 不能学排序算法学傻了吧,这题不至于上各种排序算法吧还
/*新建一个数组先把原数组中的奇数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 回复(36)
从题目得出的信息:
相对位置不变--->保持稳定性;奇数位于前面,偶数位于后面 --->存在判断,挪动元素位置;
这些都和内部排序算法相似,考虑到具有稳定性的排序算法不多,例如插入排序,归并排序等;这里采用插入排序的思想实现。
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 回复(17)
这道题考察的排序。
这题这一看,分成两部本,太开心了,原来是快排的变种,于是写了程序,后来结果大家知道了,肯定不满足相对位置不变这个条件。因为快排本身就是不稳定的算法,稳定高效的排序算法常用的只有归并了,堆排也是不稳定的。所以,用归并排序的思想解决较合适。时间复杂度低。代码如下:

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)
新开数组空间换时间的解法,
? ? 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)











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 回复(3)
时间复杂度为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)
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 回复(4)

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)
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)

扫一扫,把题目装进口袋

??屯?,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注??屯诤?/p>

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京??涂萍加邢薰?/li>
  • 联系方式:010-60728802(电话) admin@www.kxiwk11.cn
  • ??涂萍?2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号