天天看点

调整数组顺序使奇数位于偶数前面(C++简单区)调整数组顺序使奇数位于偶数前面解题思路一解题思路二解题思路三

调整数组顺序使奇数位于偶数前面

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

示例:

输入:nums = [1,2,3,4]

输出:[1,3,2,4]

注:[3,1,2,4] 也是正确的答案之一。

提示:

1 <= nums.length <= 50000

1 <= nums[i] <= 10000

解题思路一

暴力解法

算法流程:

  1. 从头开始遍历,将遍历到的奇数放在另一个vector数组中
  2. 将当前奇数从原始容器中删除
  3. 将当前迭代器回指一位(因为erase执行完后返回的是删除元素的后一位(- -操作是为了防止越界))
  4. 循环上述操作直到遍历完原始容器
  5. 将原始容器中剩余的元素(所剩的皆为偶数)插入到新容器的末尾

代码如下(示例):

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        vector<int>v;
        for(vector<int>::iterator it=nums.begin();it!=nums.end();it++)
        {
            if(*it%2!=0)
            {
                //当前元素为奇数就放入v容器中
                v.push_back(*it);
                //在当前容器中删除此元素
                nums.erase(it);
                //此处减一是因为erase执行完后返回的是删除元素的后一位(--是为了防止越界)
                it--;
            }
        }
        if(nums.empty()) return v;
        else
        {
            v.insert(v.end(),nums.begin(),nums.end());
            return v;
        }
    }
};
执行用时:1320 ms, 在所有 C++ 提交中击败了5.84%的用户
内存消耗:18.6 MB, 在所有 C++ 提交中击败了7.18%的用户
           

结论:上述方法不论时间还是空间效果都极差。

解题思路二

首尾双指针法

算法流程:

  1. 定义两个指针,让它们分别指向容器的头和尾
  2. 头指针循环找到容器中第一个偶数
  3. 尾指针循环找到容器中第一个奇数
  4. 将奇数和偶数交换在容器中的位置
  5. 重复2、3、4步直到两指针会合结束循环

代码如下:

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
       if(nums.empty()||nums.size()==1) return nums;
       int n=nums.size();
       int i=0,j=n-1;
       while(i<j)
       {
           //从前往后找到第一个偶数
            while(i<j && (nums[i]&1)!=0) i++;
            //从后往前找到第一个奇数
            while(i<j && (nums[j]&1)==0) j--;
            将这两个奇数和偶数交换
            if(i<j)
            {
                int tem=nums[i];
                nums[i]=nums[j];
                nums[j]=tem;
            }
        }
    return nums;
    }
};
执行用时:40 ms, 在所有 C++ 提交中击败了85.99%的用户
内存消耗:17.7 MB, 在所有 C++ 提交中击败了74.78%的用户
           

解题思路三

快慢指针法

算法流程:

  1. 定义两个快慢指针,让它们同时指向容器的头部
  2. 快指针开始遍历容器找到容器中第一个奇数
  3. 当快指针找到奇数时将它于慢指针所指元素交换,同时移动慢指针指向下一位
  4. 交换完后让快指针继续遍历找到奇数,,然后继续与慢指针所指元素交换,直找到容器末尾结束

代码如下:

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
       if(nums.empty()||nums.size()==1) return nums;
       int fast=0,low=0;
       while(fast<nums.size())
       {
           if((nums[fast]&1)!=0)
           {
               swap(nums[fast],nums[low]);
               low++;
           }
           fast++;
       }
       return nums;
    }
};
执行用时:40 ms, 在所有 C++ 提交中击败了85.99%的用户
内存消耗:17.6 MB, 在所有 C++ 提交中击败了94.31%的用户