题目描述


需要保证奇数和奇数,偶数和偶数之间的相对位置不变,这和书本不太一样。

解题思路


方法一:创建一个新数组,时间复杂度 O(N),空间复杂度 O(N)。

public void reOrderArray(int[] nums)
{
    //奇数个数
    int oddCnt = 0;
    for(int x:nums)
        if(!isEven(x))
            oddCnt++;
    int[] copy = nums.clone();
    int i = 0, j = oddCnt;
    for(int num:copy)
    {
        if (num % 2 == 1)
            num[i++] = num;
        else
            nums[j++] = num;
    }
}


private boolean isEven(int x)
{
    return x % 2 == 0;
}

方法二:使用冒泡思想,每次都当前偶数上浮到当前最右边。时间复杂度O(N),空间复杂度O(1)。时间换空间。

public void reOrderArray(int[] nums)
{
    int N = nums.length;
    for(int i = N - 1; i > 0; i--)
    {
        for(int j = 0; j < i; j++)
            if(isEven(nums[j]) && !isEven(nums[j+1]))
            {
                swap(nums, j, j+1);
            }
    }
}

private boolean isEven(int x)
{
    return x%2 == 0;
}

private void swap(int[] nums, int i, int j)
{
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}
12-30 07:24