首页 > 试题广场 > 调整数组顺序使奇数位于偶数前面
[编程题]调整数组顺序使奇数位于偶数前面
  • 热度指数:783027 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
推荐
    /**
     * 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 回复(101)
public class Solution {
    public void reOrderArray(int [] array) {
        int k=0;//用来记录当前已经排好序的奇数位置的个数
        for(int i =0;i<array.length;i++){
            if(array[i]%2==1){//遇到偶数继续往下遍历,直到当前为奇数
                int j=i;//用j来记录当前奇数的位置
                while(j>k){//当前的位置到k的位置,进行交换
                    int temp =array[j];
                    array[j]=array[j-1];
                    array[j-1]=temp;
                    j--;
                }
                k++;
            }
        }
    }
}

发表于 2020-05-29 10:45:50 回复(0)

public class Solution {
     public static void reOrderArray(int [] array) {
        for (int bound = 0; bound < array.length; bound++) {
            // 判断该元素是否是奇数
            if (array[bound] % 2 == 1) {
                // 用一个空间保存当前数据
                int tmp = array[bound];
                int cur = bound - 1;
                // 判断该奇数前边是否有偶数,有的话,将偶数往后移一个位置
                for (; cur >= 0; cur--) {
                    if (array[cur] % 2 == 0) {
                        array[cur + 1] = array[cur];
                    }else {
                        // 当 cur 位置是奇数,就结束循环
                        break;
                    }
                }
                // bound 位置奇数放到 cur 位置后边
                array[cur + 1] = tmp;
            }
        }
    }
}



编辑于 2020-05-28 23:59:35 回复(0)
public class Solution {
    public void reOrderArray(int [] array) {
        int[] array1 = new int[array.length];
            int jicount = 0;
            int a=0;
            for(int i = 0;i<array.length;i++){   //计算奇数的个数
                if(array[i]%2==1){
                    jicount++;
                }
            }
            for(int i = 0;i<array.length;i++){
                if(array[i]%2==1){
                    array1[a]=array[i];
                    a++;
                }else{
                    array1[jicount]=array[i]; //从奇数后面开始放偶数
                    jicount++;
                }
            }
            for(int i = 0;i<array1.length;i++){
                array[i]=array1[i];
            }
    }
}

编辑于 2020-05-26 16:12:29 回复(0)
空间换时间,拷贝原数组,建立双指针分别记录奇偶数的起始位置。
import java.util.*;
public class Solution {
    public void reOrderArray(int [] arr) {
        if(arr.length==0)
            return;
        int numodd=0;
        for(int i=0;i<arr.length;i++)
            if((arr[i]&1)!=0)
                numodd++;
        int[] res=Arrays.copyOf(arr,arr.length);
        int ji=0,ou=numodd;
        for(int i=0;i<arr.length;i++){
            if((res[i]&1)!=0)
                arr[ji++]=res[i];
            else arr[ou++]=res[i];
        }
    }
}

发表于 2020-05-19 14:32:07 回复(0)
public static class Solution {
	    public void reOrderArray(int [] array) {
	        StringBuffer jsbuf = new StringBuffer();
	        StringBuffer osbuf = new StringBuffer();
	        for(int i=0; i < array.length; i++) { 
	        	if(array[i]%2==1) {
	        		jsbuf.append(array[i]).append(",");
	        	}else {
	        		osbuf.append(array[i]).append(",");
	        	}
	        }
	        jsbuf.append(osbuf);
	        jsbuf.deleteCharAt(jsbuf.length()-1);
	        Arrays.asList(jsbuf.toString());
	        
	    }
	}

发表于 2020-05-09 17:21:11 回复(1)
1.插入法
  public static void reOrderArray(int [] array) {
        for(int i=0;i<array.length;i++)
        {
            if(array[i]%2==0)
            {
                continue;
            }
            else
            {
                //如果是奇数
                int j=0;
                //保存要插入的值
                int a=array[i];
                boolean isFind =false;
                while (j<i)
                {
                    if(array[j]%2==0)
                    {
                        isFind = true;
                        break;
                    }
                    j++;
                }
                if(isFind)
                {
                    //将 j后面的数据后移
                    for(int k=i;k>=j+1;k--)
                    {
                        array[k]= array[k-1];

                    }
                    array[j]=a;
                }

            }
        }
    }


发表于 2020-05-07 22:22:42 回复(0)
public class Solution {
    public void reOrderArray(int [] array) {
        int [] newArray = new int[array.length];
        //指针left、right指向新数组的首尾         
        int left=0,right =newArray.length-1;
        //指针i,j指向旧数组的首尾,遍历旧数组
        for(int i = 0,j=newArray.length-1;i<newArray.length;i++,j--){
            if((array[i]&1)==1){
                //i遇到奇数,插入新数组的首部
                newArray[left]=array[i];
                left++;
            }
            if((array[j]&1)==0){
                //j遇到偶数,插入新数组的尾部
                newArray[right]=array[j];
                right--;
            }
        }
 //遍历新数组,把值赋给旧数组
        for(int i=0;i<newArray.length;i++){
        array[i] = newArray[i];
        } 
    }
}
使用四个指针解决。首先开辟一个新的数组,使用两个指针i,j指向旧数组的首尾,再使用两个指针left,right指向新数组的首尾,利用指针i,j扫描旧组数,i指针遇到奇数就根据letf指针的索引存入新数组头中,j指针遇到偶数就根据right指针的索引存入新数组的尾中,遍历一遍后新数组就是排序好的数组,然后再次遍历新数组,把值赋给旧数组就ok了。
时间复杂度O(N),空间复杂度O(N)。
编辑于 2020-05-05 16:29:50 回复(0)
普通的解法:
1、将给定数组按顺序分成只含奇数的数组和只含偶数的数组;
2、将两个数组按顺序存放到原数组中。
(开冰箱门->放大象->关冰箱门)
public class Solution {
    public void reOrderArray(int [] array) {
        int[] arr1 = new int[array.length];
        int[] arr2 = new int[array.length];
        int count1=0,count2=0;
        for(int i=0;i<array.length;i++){
            if(array[i]%2==1){
                arr1[count1++] = array[i];
            }else
                arr2[count2++] = array[i];
        }
        for(int i =0;i<count1;i++){
            array[i] = arr1[i];
        }
        for(int i =0;i<count2;i++){
            array[count1+i] = arr2[i];
        }
    }
}


发表于 2020-05-01 22:51:57 回复(0)
//这题与小米的题目很像,我的相关是设置左右标记,以及中间数组用于了临时存储改变的数组
public class Solution {
    public void reOrderArray(int [] array) {
        int[] temp = new int[array.length];
        int left = 0;
        int right = array.length - 1;
        for(int i = 0;i<array.length;i++){
            if(array[i]%2!=0)
                temp[left++] = array[i];
            else
                temp[right--] = array[i];
        }
        
        //重新赋值给array,注意一点由于偶数是从后往前赋值,因此在替换的时候要注意换回来
        //先要将右索引归还
        right = array.length-1;
        for(int i = 0;i<array.length;i++){
            if(i<left)
                array[i] = temp[i];
            else{//偶数要从后面往前赋值
                array[i] = temp[right--];
            }
        
        }
    }
}
复杂度应该不高
发表于 2020-04-29 15:09:23 回复(0)
//开辟两个栈存储奇偶数,然后依次出栈放入数组中。
/./我的解法是不是最垃圾的。
import java.util.Stack;
public class Solution {
    public void reOrderArray(int [] array) {
        Stack<Integer> stack1 = new Stack();
        Stack<Integer> stack2 = new Stack();
        for(int i=0; i<array.length ; i++){
            if(array[i] % 2 == 0){
                //偶数
                stack1.push(array[i]);
            }else{
                //奇数
                stack2.push(array[i]);
            }
        }
        
        for(int n = array.length-1; n >= 0 ; n--){
            if(!stack1.empty()){
                array[n] = stack1.pop();
            }else{
                array[n] = stack2.pop();
            }

        }
        
    }

}
发表于 2020-04-26 14:33:07 回复(0)

利用插排的思想就好了,是奇数就前移。
例子:{1,2,3,4,5,6,7,8}
当i=0时,项为奇数,位置不变,游标为1;
当i=1时,项为偶数,位置不变,游标为1;
当i=2时,项为奇数,位置前移,偶数从游标位置1向后移动至i=2;
.
.
.
即可。



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


发表于 2020-04-22 12:00:53 回复(0)
import java.util.*;
public class Solution {
    public void reOrderArray(int [] array) {
        List<Integer> ji = new ArrayList<Integer>();
        List<Integer> oo = new ArrayList<Integer>();

        for(int i = 0 ;i <array.length;i++){
            if(array[i]%2 == 0){
                oo.add(array[i]);
            }
            else{
                ji.add(array[i]);
            }
        }
        int m = 0;
        for(int i = 0 ;i <ji.size();i++){
            array[m] = ji.get(i);
            m++;
        }
        for(int i = 0 ;i <oo.size();i++){
            array[m] = oo.get(i);
            m++;
        }
    }
}
发表于 2020-04-19 12:22:30 回复(0)
public void reOrderArray(int[] array) { if (array == null || array.length < 2) { return;  } int length = array.length;  int left = 0, right;  while (left < length) { if (!isOdd(array[left])) {//从左向右 把偶数扔到右边  right = left + 1;  int count = 0;//表示互换的两个数之间的偶数数量;  while (!isOdd(array[right])) {//向右继续寻找,如果找到的是偶数继续向右,如果是奇数则两者互换  if (right++ == length - 1) return;  count++;  } //找到left后面 第一个奇数 两者互换  int temp = array[left];  array[left] = array[right];  if (count > 0) {//中间还有其他偶数,为了保持有序  System.arraycopy(array, left + 1, array, left + 2, count);//left+2开始count个值,右移一位  }
         array[left + 1] = temp;   }
      left++;  }
} private boolean isOdd(int num) { return (num & 1) == 1; }

发表于 2020-04-17 22:42:33 回复(0)
可以效仿插入排序时,前面元素后移让出正确的位置给待插入的元素。
public class Solution {
    public void reOrderArray(int [] array) {
        if (array.length <= 1) return;
        int idx = 1;
        while (idx < array.length) {
            int i = idx;
            if (array[idx] % 2 == 1) {
                int temp = array[idx];
                while (i - 1 >= 0 && array[i - 1] % 2 == 0) {//注意这里要先判断i-1,否则会越界
                    array[i] = array[i - 1];
                    --i;
                }
                array[i] = temp;
            }
            ++idx;
        }
    }
}

发表于 2020-04-16 00:21:53 回复(0)

//每次遍历遇到偶数后,都判断后面是否有奇数,如果有,则将奇数移到偶数的位置
//并把数组从该偶数位置向后移动一个位置,(插入排序思想)

public class Solution {     public static void main(String[] args) {         int[] arr = {1,2,3,4,5,6,7};         reOrderArray(arr);      }     public static void reOrderArray(int [] array) {         int len = array.length;         int index = 0;         for (int w = 0;w < len; w ++)          for (int i = w; i < len; i++){             if (array[i]%2 == 0){                 int j = i;                 while (j < len){                     if (array[j]%2 == 1){                         int tmp = array[j];                         while (j > i){                             array[j] = array[j-1];                             j --;                         }                         array[i] = tmp;                         break;                     }                     j++;                 }             }         }         // System.out.print(array);     } }

编辑于 2020-04-08 21:03:12 回复(0)

干嘛要插入移来移去呢?不能定义两个指针一个从前一个从后找嘛?是不是有啥弊端,望告知!!

  • 这是我做的,如果最后赋值回array,这里的编译器好像识别,害我纠结了半天。

    public class Solution {
    
      public void reOrderArray(int [] array) {
    
    
    int[] re = new int[array.length];
    int lo = 0;
    int hi = array.length-1;

    for(int i=0, j=array.length-1;i<array.length&&j>=0;i++,j--){
        if(array[i]%2 != 0){
            re[lo] = array[i];
            lo++;
        }
        if(array[j] % 2 == 0){
            re[hi] = array[j];
            hi--;
        }

    }
    array = re.clone();

    for (int temp:array
         ) {
        System.out.print(temp);
    }

}

public static void main(String[] args) {
    Solution solution = new Solution();
    Scanner scanner = new Scanner(System.in);
    System.out.println("n is :");
    int n = scanner.nextInt();
    int[] a = new int[n];

  for(int i=0;i<n;i++){
      a[i] = scanner.nextInt();
  }
    solution.reOrderArray(a);

}

}

```

编辑于 2020-04-04 15:30:13 回复(0)
这是leetcode上的答案,在这里为什么通不过呢,各位大佬看看

public class Solution {
    public void reOrderArray(int [] array) {
      int i = 0, j = array.length - 1, tmp;
        while(i < j) {
            while(i < j && (array[i] & 1) == 1) i++;
            while(i < j && (array[j] & 1) == 0) j--;
            tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }
}
发表于 2020-04-03 16:24:56 回复(0)
我的思路是遍历数组,当遇到偶数的时候停下,记录数组下标。再向前遍历,当遇到奇数时,将所有偶数逐次后移再将奇数插入。回到记录的数组下标接着遍历,直到数组遍历完成。
public class Solution {
    public void reOrderArray(int [] array) {
        if(array==null||array.length==0)return ;//判断数组为空
        int temp=0;
        boolean flag = false;
        for(int i=0,j=0;i<array.length&&j<array.length;i++,j++){
            if(judge(array[j])){//为偶数时
                flag=true;//将标志位置为0
                i--;//为了保证i始终记录当前值,将i不断减1
                continue;
        }else if(flag){//如果遇到偶数后再遇到奇数,进行逐次移位
                temp=array[j];
                for(;j>i;j--){
                    array[j]=array[j-1];
                }
                array[i]=temp;
                flag=false;
            }
        }
    }
    
    public boolean judge(int num){
        return (num&1)==1?false:true;//判断奇偶比较高效的方式
    }
}
发表于 2020-03-26 22:37:03 回复(0)
 public class Solution {
    public void reOrderArray(int[] array){
           //创建辅助数组
            int res[] = new int[array.length];
            int len = array.length;
            // 记住存的奇数个数
            int count = 0;

            //寻找奇数 存到数组前面
            for (int i = 0; i < len; i++) {
                if (array[i] % 2 != 0){
                    res[count] = array [i];
                    count ++;
                }
            }

           //把偶数存到数组后面
            for (int i = 0; i < len; i++) {
                if (array[i] % 2 == 0){
                    res[count] = array [i];
                    count++;
                }
            } 
        array = res;
    }
}
问下,我这哪里出粗了,本地试的没问题哇,思路是 :新建一个辅助数组,奇数,放到数组前面,再遍历一遍,把偶数放到奇数后面
编辑于 2020-03-25 23:22:56 回复(0)
使用两个临时数组存放奇数和偶数,复杂度O(2n)
public class Solution {
    public void reOrderArray(int [] array) {
        //存放奇数
        int arrayL[]=new int[array.length];
        //存放偶数
        int arrayR[]=new int[array.length];
        //奇数计数器
        int countL=0;
        //偶数计数器
        int countR=0;
        for(int i=0;i<array.length;i++){
            if(array[i]%2!=0){
                arrayL[countL]=array[i];
                countL++;
            }else{
                arrayR[countR]=array[i];
                countR++;
            }
        }
        int max=0;
        if(Integer.compare(countL,countR)>=0){
            max=countL;
        }else{
            max=countR;
        }
        for(int i=0;i<max;i++){
            if(i<countL){
                 array[i]=arrayL[i];
            }
            if(i<countR){
                array[i+countL]=arrayR[i];
            }
        }
    }
}

编辑于 2020-03-24 15:39:25 回复(0)

问题信息

难度:
320条回答 256619浏览

热门推荐

通过挑战的用户

查看代码