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

2021年5月30日 76Browse 1Like 0Comments

题目描述

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

示例:

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

提示:

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

解题思路

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

方法一 两层循环

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

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

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(n^2)$

空间复杂度为:$O(1)$

毫无疑问,超时了!!!

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

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(n^2)$

空间复杂度为:$O(1)$

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

方法二 一层循环

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

代码如下所示:

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(1)$

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

agedcat_xuanzai

这个人很懒,什么都没留下

Comments