一道对时间复杂度和空间复杂度都有要求的算法题,求解?解决思路

一道对时间复杂度和空间复杂度都有要求的算法题,求解?
给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。要求：空间复杂度O(1)，时间复杂度为O（n）。

------解决方案--------------------
两个指针，一个从左边，一个从右边
当左边是偶数，右边是奇数时交换两个数
------解决方案--------------------

Java code


public int[] process(int[] array){
        int j=1;
        for(int i=0;i<array.length-1;i++){
            if(j<array.length){
                if(array[i]%2==0){
                    if(array[j]%2!=0){
                        swap(array,i,j);
                    }
                    else{
                        j++;
                        i--;
                    }
                }
            }
        }
        return array;
    }
    public void swap(int[] array,int a,int b){
        int temp=array[a];
        array[a]=array[b];
        array[b]=temp;
    }
    public static void main(String[] args) {
        int[] a={2,5,4,3,9,7,6,3,1};
        int[] b=new Array().process(a);
        System.out.println(Arrays.toString(b));
    }

结果打印：[5, 3, 9, 7, 3, 1, 6, 4, 2]

一道对时间复杂度和空间复杂度都有要求的算法题,求解?解决思路

相关推荐