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

╰半夏微凉° 2022-12-27 01:53 17阅读 0赞

**题目内容：**

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

**示例：**

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

**提示：**

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

--------------------

**思路：**

*  双指针，头尾同时遍历，将从前往后遍历到的第一个偶数与从后向前遍历到的第一个奇数交换，然后重复上述动作，直到两指针相遇。

**代码：**

class Solution { 
    public:
        vector<int> exchange(vector<int>& nums) { 
            //一个指标在前一个指标在后
            //前面的如果遇到偶数则停住,然后和后面的互换
            //后面的如果遇到奇数则停住,然后和前面的互换
    
            int left =0 , right = nums.size()-1;
            while(left<right){ 
                if((nums[left]&1) != 0){ //代表是奇数
                    left++;
                    continue;
                }
                if((nums[right]&1) == 0){ //代表是偶数
                    right--;
                    continue;
                }
                swap(nums[right--],nums[left++]);
            }
            return nums;
        }
    };

时间复杂度 O(N) ： N 为数组 nums 长度，双指针 i, j 共同遍历整个数组。  
空间复杂度 O(1)： 双指针 i, 使用常数大小的额外空间。

参考：[剑指题解][Link 1]  
**reflection：** 现在是看到这种简单的题目脑子里面知道用快慢指针做了，但是代码写得很糟糕没办法秒掉，继续加油。— 2020.12.7

[Link 1]: https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/solution/qian-hou-zhi-zhen-by-hou-zi-10/