首页 > 试题广场 >

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

[编程题]调整数组顺序使奇数位于偶数前面

热度指数：887021 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

算法知识视频讲解

推荐

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

txy_钟琛

public class Solution {
    public void reOrderArray(int [] array) {
        int k = 0;
        for (int i = 0; i < array.length; i++) {
            if ((array[i] & 1) == 1) {//从左向右，每次遇到的，都是最前面的奇数，一定将来要被放在k下标处
                int temp = array[i];//现将当前奇数保存起来
                int j = i;
                while (j > k){//将该奇数之前的内容(偶数序列)，整体后移一个位置
                    array[j] = array[j-1];
                    j--;
                }
                array[k++] = temp;//将奇数保存在它将来改在的位置，因为我们是从左往右放的，没有跨越奇 数，所以一定是相对位置不变的
            }
        }
    }
}

发表于 2022-05-24 11:44:35 回复(0)

Java

此生最爱ntr

import java.util.Arrays;

public class Solution1 {
    public void reOrderArray2(int[] array) {
        int[] a = new int[array.length];
        int b = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 != 0) {
                a[b] = array[i];
                b++;
            }
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 0) {
                a[b] = array[i];
                b++;
            }
        }
        System.out.println(Arrays.toString(a));
    }

    public static void main(String[] args) {
        int[] arr1 = { 1, 2, 3, 4, 5, 6, 7 };
        int[] arr2 = { 2, 4, 6, 1, 3, 5, 7 };
        int[] arr3 = { 1, 3, 5, 7, 2, 4, 6 };
        int[] arr4 = { 1 };
        int[] arr5 = { 2 };
        int[] arr6 = {};
        Solution1 s = new Solution1();
        s.reOrderArray2(arr1);
        s.reOrderArray2(arr2);
        s.reOrderArray2(arr3);
        s.reOrderArray2(arr4);
        s.reOrderArray2(arr5);
        s.reOrderArray2(arr6);
    }
}

这个问题卡了我一个半小时，当时还以为题太难，我的代码不对，结果在本地上运行成功，心态崩了，白瞎我这半个小时。

发表于 2022-03-08 16:30:19 回复(1)

Java

路平

//权当温习一下归并排序（<=时则为稳定性排序），修改一下比较规则即可
public class Solution {
    public void reOrderArray(int [] array) {
        //运用归并排序
        if (array == null || array.length < 1) {
            return ;
        }
        mergeSort(array, 0, array.length - 1);
    }
    public void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return ;
        }
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
    public void merge(int[] arr, int left, int mid, int right) {
        if (left >= right) {
            return ;
        }
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (compare(arr[i], arr[j])) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        if (i <= mid) {
            for (; i <= mid; i++) {
                temp[k++] = arr[i];
            }
        } else {
            for (; j <= right; j++) {
                temp[k++] = arr[j];
            }
        }
        k = 0;
        for (i = left; i <= right; i++) {
            arr[i] = temp[k++];
        }
    }
    public boolean compare(int x, int y) {
        if (x % 2 == 1) {
            return true;
        }
        if (y % 2 == 1) {
            return false;
        }
        return true;
    }
}

编辑于 2021-02-08 13:01:30 回复(0)

Java

匿迹小王子

    /**
     * 解决思路：因为要求相对位置保持不变，所以不能使用指针法。
     * 可以使用冒泡排序或者归并排序。
     *
     * @author freedom wang
     * @date 2021-01-23 13:35:37
     */
    public void reOrderArray(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }

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

    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

发表于 2021-01-23 20:36:46 回复(0)

Java

努力学习的中国好青年

import java.util.*;

public class Solution {
    public void reOrderArray(int [] array) {
        ArrayList<Integer> odd = new ArrayList<>();
        ArrayList<Integer> even = new ArrayList<>();
        for (int i = 0;i < array.length;i++) {
            if (array[i] % 2 != 0) {
                odd.add(array[i]);
            }else {
                even.add(array[i]);
            }
        }
        
        for (int i = 0;i < odd.size();i++) {
            array[i] = odd.get(i);
        }
        
        for (int j = odd.size();j < array.length;j++) {
            array[j] = even.get(j-odd.size());
        }
    }
}

发表于 2021-01-15 16:09:27 回复(0)

Java

牛客441059753号

import java.util.Arrays;

public class Solution {
public void reOrderArray(int [] array) {
for (int i = 0; i < array.length-1; i++) {
for (int j = i+1; j < array.length; j++) {
if (array[i] % 2 == 0 && array[j] % 2 !=0){
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
}
System.out.println("array.toString() = " + Arrays.toString(array));
}
}

发表于 2021-01-12 10:20:25 回复(0)

Java

yjies

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

发表于 2021-01-06 10:11:38 回复(0)

Java

Lancr

解法1:

Running time O(N^2), Space O(1)

Insertion sort的变形，数组需要交换的条件只有Even, Odd(个人感觉这题没必要写交换，不如空间直观)

import java.util.*;
public class Solution {
    public void reOrderArray(int [] array) {
        for(int i= 0; i < array.length;i++){
            for(int j = i; j >0; j--){
                if(i>=1){
                    if((array[j] % 2 == 1) && array[j-1] % 2 ==0){
                        int temp = array[j-1];
                        array[j-1] = array[j];
                        array[j] = temp;
                    }
                }
            }
        }
    }
}

解法2:

Running time O(N), Space O(N)

直接判断奇偶，然后从新数组中加入结果并替换原数组

import java.util.*;
public class Solution {
    public void reOrderArray(int [] array) {
        ArrayList<Integer> odd_arr = new ArrayList();
        ArrayList<Integer> even_arr = new ArrayList();
        for(int p:array){
            if(p % 2 ==1){
                odd_arr.add(p);
            }
            else{
                even_arr.add(p);
            }
        }
        odd_arr.addAll(even_arr);
        for(int i =0; i < array.length; i++){
            array[i] = odd_arr.get(i);
        }
    }

发表于 2020-12-28 08:25:20 回复(0)

Java

张粤利

public class Solution {
    public void reOrderArray(int [] array) {
        int[]ou=new int[array.length];
        int[]ji=new int[array.length];
        int a=0;
        int b=0;
        for(int i=0;i<array.length;i++){
            if(array[i]%2==0){
                ou[a]=array[i];
                a++;
            }else{
                ji[b]=array[i];
                b++;
            }
        }
        for(int j=0;j<b;j++){
            array[j]=ji[j];
        }
        for(int j=0;j<a;j++){
            array[b+j]=ou[j];
        }
    }
}

发表于 2020-11-23 14:57:21 回复(0)

Java

温澜潮生11

类似于快排的partition问题，快排要分为小于大于，等于三个部分，所以需要两个变量less,more来分开，还有一个是cur。而这要分为奇数偶数，需要一个变量mid，还需要cur。
快排一直让less和more处于分界处。
而这个只有一个变量的时候可以先让mid走几步，走到偶数的地方，让它表示第一个开始的偶数，然后cur再等于它的下一个，开始循环。
如果此时是偶数就跳过，是奇数（此时要把这个数插入到mid之前的一个位置，把mid到这个数之间的数全都后移）则将cur此时值保存，mid到cur的偶数全部向后移动，将cur插入mid的地方，mid++，cur++；（因为这里要求是不能改变位置，所以不能直接把奇数交换到后面，而得所有值都向后移动）

这种操作就和快排一样，O（nlogn），因为每操作一个奇数都需要移动mid处到它位置处的所有值。

public class Solution {
    public void reOrderArray(int [] array) {
        int mid=0;//作为第一个偶数的分割点
        while(mid<array.length && (array[mid] & 1) ==1){
            mid++;
        }
        int cur=mid+1;//既然退出循环，说明这个值就是偶数,记得别用mid++,因为用了之后mid也会+1
        while(cur<array.length){
            if((array[cur] & 1) ==0){//如果是偶数，则不用操作
                cur++;
            }else{//如果是奇数，则需要将它向前移动到mid的位置，而mid位置到这个数的位置的值全部向后移动
                int num=array[cur];
                int index=cur-1;
                while(index+1<array.length && index>=mid){
                    array[index+1]=array[index];
                    index--;
                }
                array[mid]=num;
                cur++;
                mid++;
            }
        }
    }
}

编辑于 2020-11-20 15:14:30 回复(0)

Java

bh阿卡丽

public class Solution {
    public void reOrderArray(int [] array) {
        for(int i=1;i<array.length;i++){
            if(array[i]%2!=0){
                for(int j=i;j>0;j--){
                   if(array[j-1]%2!=0) {break;}
                    else {
                    int temp=array[j-1];
                     array[j-1]=array[j];
                    array[j]=temp;
                }}
            }
        }
    }
}
碰到奇数与前面一个一个对比交换知道碰到前面的是偶数为止

发表于 2020-11-10 14:53:03 回复(0)

Java

JaxonSuzy

public class Solution {
    public void reOrderArray(int [] array) {
        int n  = array.length;
        int[] res = new int[n];
        int ji=0;
        int ou = n-1;
        for(int i=0;i<n;i++){
            if(array[i]%2==1) res[ji++] = array[i];
            if(array[n-i-1]%2==0) res[ou--] = array[n-i-1];
        }
        for(int i=0;i<n;i++){
            array[i] = res[i];
        }
    }
}

发表于 2020-11-04 20:23:06 回复(0)

Java

tornado123

    /**
    题目描述
    输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，
    所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
    题解：
    要保证原有的次序，则只能顺次移动或者是相邻交换
    i 从左向右开始遍历，找到第一个偶数
    j 从 i+1 开始遍历，知道找到第一个奇数
    将 i，……，j-1 的元素整体后移一位，最后将找到的奇数放入 i 位置中， 然后再 i++
    */
    public void reOrderArray(int [] array) {
        int i = 0, j = 1,  len = array.length;
        int temp;
        while (true) {
            // 左指针 i 找到第一个 偶数
            while (i < len && array[i] % 2 == 1) {
                i ++;
            }
            // 右指针 j 找到第一个 奇数
            j = i + 1;
            while (j < len && array[j] % 2 == 0) {
                j++;
            }
            if (j >= len) {
                // 终止条件
                break;
            }
            // 将 i，……，j-1 的元素整体后移一位，最后将找到的奇数放入 i 位置中，
            temp = array[j];
            for (int k = j - 1; k >= i; k--) {
                array[k + 1] = array[k];
            }
            array[i] = temp;
            // 更新 i 值
            i++;
        }
    }

发表于 2020-10-04 16:11:21 回复(0)

Java

gelatin

public class Solution {
    public void reOrderArray(int [] array) {
        int write = 0;
        for (int read = 0; read < array.length; read++){
            if ((array[read]&1) == 1){
                int tmp = array[read];
                for (int i = read-1; i >= write; i--){
                    array[i+1] = array[i];
                }
                array[write] = tmp;
                write += 1;
            }
            
        }
    }
}

time: O(n^2)

space: O(1)

发表于 2020-09-12 10:33:44 回复(0)

Java

BowinChow

//利用表，一半奇数，一半偶数遍历，然后再组合；

import java.util.List;

import java.util.ArrayList;
public class Solution {
public void reOrderArray(int [] array) {
List<Integer> odd = new ArrayList<>();
List<Integer> even = new ArrayList<>();
int n=array.length;
for(int i=0; i<n;i++){
if(array[i]%2 == 1){
odd.add(array[i]);
}else{
even.add(array[i]);
}
}
for(Integer s:even){
odd.add(s);
}

for(int i=0; i<odd.size();i++){
array[i]=odd.get(i);
}
}
}

发表于 2020-09-10 17:22:53 回复(0)

Java

crx9527

public static void reOrderArray(int [] array) {
    int[] res = new int[array.length];
    int n = 0;
    for(int i = 0;i<array.length;i++){
        if((array[i]%2)==1){
            res[n++]=array[i];

        }
    }
    for(int i = 0;i<array.length;i++){
        if((array[i]%2)==0){
            res[n++]=array[i];

        }
    }
    System.arraycopy(res, 0, array, 0, res.length);
}

新建一个数组，遍历原数组依次选出奇数放入新数组，再次遍历选出偶数依次放入，然后将新数组赋值给原数组

发表于 2020-09-03 10:04:37 回复(0)

Java

Hammand

遍历一次数组，减少额外空间O(n/2)

public void reOrderArray(int [] array) {
    //使用队列方便后面取数据
    Queue<Integer> even = new LinkedList();
    int i = 0;
    for (int n = 0; n < array.length; n++){
        if((array[n] & 1) == 1){
            //奇数部分直接加入原数组
            array[i++] = array[n];
        }else{
            //偶数部分最后加
            even.add(array[n]);
        }
    }
    while(!even.isEmpty()){
        array[i++] = even.poll();
    }
}

发表于 2020-08-24 21:20:37 回复(0)

Java

顾依

如果是奇数，就往前移动，start是当前奇数应该插入的位置。

public class Solution {
    public void reOrderArray(int [] array) {
       int start=0;
        int tmp=0;
        for(int i=0;i<array.length;i++)
        {
            if(array[i]%2==1)
            {
                tmp=array[i];
                for(int j=i-1;j>=start;j--)
                    array[j+1]=array[j];
                array[start]=tmp;
                start++;
            }
        }
}
}

发表于 2020-08-20 17:42:40 回复(0)