调整数组顺序使奇数位于偶数前面(思路和实现)

KLQ 2020-05-08 10:11:00 java常见问答 4600

今天要给大家分享的实例是和调整数组顺序使奇数位于偶数前面相关的内容,具体的介绍了几种思路和实现方式,一起来详细的了解一下吧。

题目:

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

思路1:

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;
}

思路2:

从题目可以了解到:

相对位置不变--->保持稳定性;奇数位于前面,偶数位于后面 --->存在判断,挪动元素位置;

这些都和内部排序算法相差不一,考虑到具有稳定性的排序算法不多,例:插入排序,归并排序等;这里采用插入排序的思想实现。

代码实现:

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++;
            }
        }
    }
}

思路3:

新建一个数组先将原数组中的奇数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;
        
    }
};

以上就是今天的实例分享了,更多实例,请继续关注奇Q工具网的java实例栏目了解吧。

推荐阅读:

判断数组是不是二叉搜索树的后序遍历的结果(思路和实现)

判断序列是否为该栈的弹出顺序,如何实现?思路分享

顺时针打印矩阵如何实现?思路和实现分享java