题目描述

  1. 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
  5. 示例：
  7. 输入：nums = [1,2,3,4]
  8. 输出：[1,3,2,4] 
  9. 注：[3,1,2,4] 也是正确的答案之一。
  12. 提示：
  14. 0 <= nums.length <= 50000
  15. 0 <= nums[i] <= 10000

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

双向遍历嘛，从左往右找偶数，从右往左找奇数，找到一对就交换数值，找到下标交叉为止

代码

  1. class Solution {
  2.     public:
  3.     vector<int> exchange(vector<int>& nums)
  4.     {
  5.         int i = 0, j = nums.size() - 1;
  6.         while (i < j)
  7.         {
  8.             while(i < j && (nums[i] & 1) == 1) i++;
  9.             while(i < j && (nums[j] & 1) == 0) j--;
  10.             swap(nums[i], nums[j]);
  11.         }
  12.         return nums;
  13.     }
  14. };

复杂度分析

O（n）的时间，空间也是O(n)