剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

1
2
3
输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。

提示：

  1. 0 <= nums.length <= 50000
  2. 1 <= nums[i] <= 10000

解题思路

这道题是简单题，思路一看就有，but，写了半天。。。

方法一 两层循环

首先想到的是，依次遍历整个数组，找到一个偶数，然后遍历它之后的元素，找到一个奇数，进行交换。循环往复，直至遍历结束。可以做一点小优化，找奇数的时候如果找不到就可以直接返回了。

具体细节可以参考以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> exchange(vector<int>& nums)
{
    bool existOdd=true;
    for(int i=0;i<nums.size();++i)
    {
        if(nums[i]%2==1) continue;
        int j=i+1;
        for(;j<nums.size();++j)
        {
            if(nums[j]%2==1)
            {
                swap(nums[i],nums[j]);
                break;
            }
        }
        if(j==nums.size()) existOdd=false;
        if(!existOdd) break;
    }
    return nums;
}

时间复杂度为：O(n2)O(n^2)

空间复杂度为：O(1)O(1)

毫无疑问，超时了！！！

然后用快慢指针的方法优化了一下，减少了操作的次数，但仍然有两层循环，第二版的代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> exchange(vector<int>& nums)
{
    int len=nums.size();
    int left=0;
    int right=0;
    while(left<len)
    {
        while(left<len&&nums[left]%2==1)
        {
            left++;
        }
        if(left>=len) break;
        right=left+1;
        while(right<len&&nums[right]%2==0)
        {
            right++;
        }
        if(right>=len) break;
        swap(nums[left],nums[right]);
        left++;
        right++;
    }
    return nums;
}

时间复杂度为：O(n2)O(n^2)

空间复杂度为：O(1)O(1)

这一版本虽然过了，但是击败了7%，丢脸的不行

方法二 一层循环

用left指针从左向右找偶数，用right指针从右向左找奇数，然后进行交换，直至相遇。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> exchange(vector<int>& nums)
{
    int len=nums.size();
    int left=0;
    int right=len-1;
    while(left<right)
    {
        if(nums[left]%2==1)
        {
            left++;
            continue;
        }
        if(nums[right]%2==0)
        {
            right--;
            continue;
        }
        swap(nums[left++],nums[right--]);

    }
    return nums;
}

时间复杂度为：O(n)O(n)

空间复杂度为：O(1)O(1)

证明了自己是个菜鸡的事实。。。