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

214个回答

添加回答
推荐
    /**
     * 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 回复(71)
//Java,用两个队列
public class Solution {
    public void reOrderArray(int [] array) {
        int length = array.length;
        Queue<Integer> quene1 = new LinkedList<Integer>();
        Queue<Integer> quene2 = new LinkedList<Integer>();
        for(int i=0;i<length;i++){
            if(array[i]%2==0){
                quene2.add(array[i]);
            }
            else{
                quene1.add(array[i]);
            }
        }
        for(int j=0;j<length;j++){
            if(!quene1.isEmpty())
                array[j] = quene1.remove();
            else
                array[j] = quene2.remove();
        }
        
        
    }
}
发表于 2019-03-20 12:39:56 回复(0)
对数组 分别进行从前到后  从后到前进行遍历
对奇数放到新数组的前面  对偶数依次从后到前放到新数组
public class Solution {
    public void reOrderArray(int [] array) {
 int result[] = new int[array.length];
        int k=0;
        int x=array.length-1;
      for(int i=0;i<array.length;i++)
      {
          if(array[i]%2!=0)
        {
            result[k++]=array[i];
        }
        if(array[array.length-i-1]%2==0)
        {
            result[x--]=array[array.length-i-1];
        }
      }
     for(int i=0;i<result.length;i++)
     {
         array[i]=result[i];
     }
}
}

发表于 2019-03-16 11:07:12 回复(0)
创建新数组
public class Solution {
    public void reOrderArray(int [] array) {
        int oddCount = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 1)
                oddCount++;
        }
        int odd = 0, even = oddCount;
        int[] newArr = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 1) {
                newArr[odd++] = array[i];
            } else {
                newArr[even++] = array[i];
            }
        }
        for (int i = 0; i < array.length; i++) {
            array[i] = newArr[i];
        }
    }
}

发表于 2019-03-12 13:50:03 回复(0)
 int jinum = 0;
        int ounum = 0;
        for(int i = 0 ; i < array.length ; i ++){
            if(array[i] % 2 == 0){
                ounum++;
            }
            if(array[i] % 2 == 1){
                jinum++;
                int num = ounum + jinum;
                for(int j = 0 ; j < ounum ; j ++){
                    num--;
                    int temp = array[num];
                    array[num] = array[num - 1];
                    array[num - 1] = temp;
                }
            }
        }

发表于 2019-03-11 22:06:39 回复(0)

想问下为什么这样写不能通过测试用例呢?本地调试是正常的啊。

public class ArrayOrder {

    public static void reOrderArray(int[] array) {
        if (array.length > 0) {
            int even = 0;
            int[] newArray = new int[array.length];
            for (int anArray : array) {
                if (anArray % 2 == 0) {
                    even++;
                }
            }
            int odd = 0;
            int even1 = 0;
            for (int anArray : array) {
                if (anArray % 2 != 0) {
                    newArray[odd] = anArray;
                    odd++;
                } else {
                    newArray[array.length - even + even1] = anArray;
                    even1++;
                }
            }
            array = newArray;
            System.out.println(array.length);
        }
    }

    public static void main(String[] args) {

        int[] array = {1, 2, 3, 4, 5, 6, 7};
        reOrderArray(array);
    }
}
发表于 2019-03-09 00:40:15 回复(0)

public class Solution {  public void reOrderArray(int [] array) {      int length = array.length-1;      int i = 0;      int j = 0;      while(j<=length)      {          if(array[j]%2==1)          {                 swap(array,i,j);                 i++;                 j++;          }else          {                                        j++;          }                        }      }    public void swap(int [] a,int begin ,int end)    {        while(begin<end)        {               int tmp = a[end];               a[end]=a[end-1];               a[end-1]=tmp;               end--;        }    } }
    指定两个标志位i和j。i指向的前面奇数最右边的数。j为向后遍历的标志。遇到偶数便利用冒泡,将这个偶数冒泡到i的位置,然后i和j都加一

发表于 2019-03-08 20:49:53 回复(0)
public class Solution {
    public void reOrderArray(int [] array) {
        if(array==null||array.length==0||array.length==1) return;
        /* 解法一 插入排序
        int oddLen = 0;
        for (int i = 0; i < array.length; i++){
            if ((array[i] & 1) == 1){
                int temp = array[i];
                int j = 0;
                for (j = i; j > oddLen; j--){
                    array[j] = array[j-1];
                }
                array[j] = temp;
                ++ oddLen;
            }
        } */
        /* 解法二 冒泡排序
        for (int i = array.length - 1; i > 0; i--){
            for (int j = 0; j < i; j++){
                if ((array[j] & 1) == 0 && (array[j+1] & 1) == 1){
                    int temp = array[j+1]; array[j+1] = array[j]; array[j] = temp;
                }
            }
        } */
        // 解法三 空间换时间 O(n)时间复杂度 O(n)空间复杂度
        int len = array.length;
        int first = 0, last = len - 1;
        int[] newArray = new int[len];
        for (int i = 0; i < len; i++){
            if ((array[i] & 1) == 1){
                newArray[first] = array[i];
                ++ first;
            }
            if ((array[len-1-i] & 1) == 0){
                newArray[last] = array[len-1-i];
                -- last;
            }
        }
        for (int i = 0; i < len; i++){
            array[i] = newArray[i];
        }
    }
}
三种解法,两个思路:
1)不开辟额外空间,时间复杂度为O(n2);对应解法一插入排序和解法二冒泡排序
2)空间换时间策略,时间复杂度O(n),空间复杂度O(n)。
我重点讲解一下第二个思路:
        新开辟一个和原数组同样大小的额外空间。用两个指针分别指向新数组的头和尾,遍历一边原数组,原数组头部如果有奇数,则复制到新数组的头部,头部++;同时原数组尾部如果有偶数,则复制到新数组的尾部,尾部--;for循环结束后,需将新数组的内容拷贝到原数组中,因为新数组是函数内部开辟的临时空间,函数结束后空间就会被释放,所以直接array = newArray是行不通的。
        欢迎各位小伙伴指出错误~
发表于 2019-03-08 19:41:52 回复(0)
public class Solution {
    public void reOrderArray(int [] array) {
        //前后两个index,各自遍历到头,一个是奇数的index(head),一个是偶数的(tail)
        //结束条件-各自遍历到头。while(head<array.length&&tail>=0)
        int head=0;
        int tail=array.length-1;
        int[] result=new int[array.length];
        int countH=0;
        int countT=result.length-1;
        while(head<array.length&&tail>=0){
            //奇数
            if(head<array.length){
                if((array[head]&1)==1){
                result[countH]=array[head];
                    ++countH;
                }
                ++head;
            }
            //偶数
            if(tail>=0){
                if((array[tail]&1)==0){
                    result[countT]=array[tail];
                    countT--;
                }
                tail--;
            }
        }
       System.arraycopy(result,0,array,0,result.length);
    }
}
//时间复杂度O(n),空间复杂度O(n)

发表于 2019-03-06 21:20:22 回复(0)
借助两个arraylist,或者借助两个数组(这两个数组长度和array长度一致),然后把奇偶分别放到不同的数组中,然后在拷贝到原数组,时间复杂度为O(n)


public void reOrderArray(int [] array) {
        ArrayList<Integer> a1 = new ArrayList<>();
        ArrayList<Integer> a2 = new ArrayList<>();
        //先进行判断奇偶数
        for (int i = 0; i < array.length; i++) {
            if(array[i]%2==0){
                //说明是偶数
                a1.add(array[i]);
            }else{
                //说明是奇数
                a2.add(array[i]);
            }
        }
        //然后把这两个list循环加到原数组中
        for (int i = 0; i < a2.size(); i++) {
            array[i] = a2.get(i);
        }
        for (int i = 0; i < a1.size(); i++) {
            array[a2.size()+i] = a1.get(i);
        }
    }

编辑于 2019-02-26 13:03:42 回复(0)
第一个想法是快速排序。。然而不稳定,之后就使用了冒泡排序了,见笑:
public class Solution {
    public void reOrderArray(int [] array) {
        boolean flag = false;
        for(int i = 1; i < array.length; i ++){
            flag = true;
            for(int j = 1; j < array.length; j ++){
                if(array[j - 1] % 2 == 0 && array[j] % 2 != 0){
                    swap (array ,j - 1, j);
                    flag = false;
                }
            }
        }
    }
    private void swap(int[] array, int a, int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

发表于 2019-02-25 14:07:31 回复(0)
public class Solution {
    public void reOrderArray(int [] array) {
        int[] array2=new int[array.length];
        int j=0;
        for(int i=0;i<array.length;i++)
        {
            if(array[i]%2==1)
            {
                array2[j]=array[i];
                j++;
            }
        }
        for(int i=0;i<array.length;i++)
        {
            if(array[i]%2==0)
            {
                array2[j]=array[i];
                j++;
            }
        }
        for(int i=0;i<array.length;i++)
        {
            array[i]=array2[i];
        }
    }
}
思路简单的时间换空间.....小学生编程思路
发表于 2019-02-23 13:05:31 回复(0)
19ms。。。
public class Solution {
    public void reOrderArray(int [] array) {
        //index记录左半边最后一个奇数的位置
        int index = -1;
        for (int i = 0; i < array.length; i++) {
            if ((array[i] & 1) == 1) {
                if (i != index + 1) {
                    for (int j = i; j > index + 1; j--) {
                        int tmp = array[j];
                        array[j] = array[j-1];
                        array[j-1] = tmp;
                    }
                }
                index += 1;
            }
        }
    }
}

发表于 2019-02-15 11:09:31 回复(0)
public class Solution {
    public void reOrderArray(int [] array) {
        int count = 0;
        for(int num:array){
            if(num % 2 != 0) count++;
        }
        int[] a = new int[array.length];
        int j = 0;
        for(int i = 0;i < a.length;i++){
            if(array[i] % 2 == 0){
                a[count++] = array[i];
            }else{
                a[j++] = array[i];
            }
        }
        System.arraycopy(a,0,array,0,a.length);
    }
}


发表于 2019-02-12 17:59:55 回复(0)
import java.util.Stack;
public class Solution {
    public void reOrderArray(int [] array) {
        Stack stack = new Stack<Integer>();
        for(int i=0;i<array.length;i++){
            if(array[i]%2==1)
                stack.push(array[i]);
        }
        for(int i=0;i<array.length;i++){
            if(array[i]%2==0)
                stack.push(array[i]);
        }
        for(int i=array.length-1;i>=0;i--){
            int temp = (Integer) stack.pop();
            array[i] = temp;
        }
    }
}
用一个栈遍历两次,跟用两个栈遍历一次,哪个会划算点呢?
发表于 2019-01-21 20:21:58 回复(0)

第一种做法: 利用插入排序的思路来做,时间复杂度为O(n^2),空间复杂度为O(1)

public void reOrderArray(int[] array) {
    for (int i = 1; i < array.length; i++) {
        for (int j = i; j > 0; j--) {
            if ((array[j] &0x1) == 1 && (array[j - 1] %0x1) == 0) {
                swap(array,j,j-1);
            }
        }
    }
}
void swap (int[] array,int i, int j){
    int temp = array[j];
    array[j] = array[i];
    array[i] = temp;
}

第二种做法是:用空间换时间,创建一个新的数组来辅助完成

public void reOrderArray_2(int[] array) {
        int oddCount = 0;
        //遍历数组,将奇数的个数找出来
        for (int i = 0; i <array.length; i++) {
            if ((array[i] & 0x1) == 1) {
                oddCount++;
            }
        }
        //拷贝原数组
        int[] copy = array.clone();
        int i = 0, j = oddCount;
        for (int num : copy) {
            //元素为奇数时
            if ((num & 0x1) == 1) {
                array[i++] = num;
            } else {
                //元素为偶数时
                array[j++] = num;
            }
        }
    }
编辑于 2019-01-14 11:38:41 回复(0)
public class Solution {
    public void reOrderArray(int [] array) {
        for(int i = 0; i < array.length; i++){
            if(array[i] % 2 == 1){
                int j = i;
                while(j >= 1 && (array[j - 1] % 2 == 0)){
                    int t = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = t;
                    j--;
                }
            }
        }
    }
}
编辑于 2019-01-10 14:30:13 回复(0)
//插入排序的思想 1 2 3 4 5 6 7 public static void adjust1(int a[])
{ //把奇数移到第一个偶数前面  for(int i=1;i<a.length;i++){ int j=i; int temp=a[i]; if(a[i]%2==0){ continue;
        }while (j>0&&a[j-1]%2==0){
            a[j]=a[j-1];
            j--;
        }
        a[j]=temp;
   }
}

发表于 2018-12-25 20:07:11 回复(0)
直接插入排序,把判断大小的条件改变成奇偶的判断,奇数就与前面比较,若前面的是偶数则前移,直到遇到奇数
 public class Solution {
     public void reOrderArray(int [] array) {
         //直接插入
         int temp = 0;
         for(int i = 1; i<array.length; i++){
             temp = array[i];
             int j = i-1;
             if(temp%2 == 1){//遇到奇数,向前移动位置
                 while(j>=0 && array[j]%2 == 0){//遇到偶数,交换位置
                     array[j+1] = array[j];
                     j--;
                 }
                 array[j+1] = temp;
             }
         }
     }
 }

编辑于 2019-02-27 20:50:20 回复(0)
import java.util.Arrays;
public class Solution {
     public void reOrderArray(int [] array) {
            int i=0;
            int a[]=new int[array.length];
      for(int k=0;k<array.length;k++)
          if(array[k]%2!=0)a[i++]=array[k];
      for(int j=0;j<array.length;j++)
          if(array[j]%2==0)a[i++]=array[j];
      for (int j = 0; j < a.length; j++) 
          array[j]=a[j];
        }
}

发表于 2018-12-24 13:43:16 回复(0)

扫一扫,把题目装进口袋

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

扫描二维码,进入QQ群

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

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