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

摘要

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

一、双指针解析

考虑定义双指针 i , j分列数组左右两端，循环执行：

• 指针 i从左向右寻找偶数；
• 指针 j从右向左寻找奇数；
• 将偶数nums[i]和奇数 nums[j]交换。

可始终保证：指针 i左边都是奇数，指针j右边都是偶数 。

算法流程：

• 初始化：i, j双指针，分别指向数组 nums左右两端；
• 循环交换： 当 i=j时跳出；
•         指针i遇到奇数则执行 i=i+1跳过，直到找到偶数；
•         指针j遇到偶数则执行 j=j−1跳过，直到找到奇数；
•          交换 nums[i]和 nums[j]值；
• 返回值：返回已修改的 nums数组

class Solution {public int[] exchange(int[] nums) {int left = 0, right = nums.length - 1;while (left < right) {while (left < right && nums[left] % 2 == 1) {left++;}while (left < right && nums[right] % 2 == 0) {right--;}if (left < right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}}return nums;}
}

复杂度分析：

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

博文参考

《leetcode》