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

解题思路：首尾双指针

算法思路：
  • 定义头指针 left，尾指针 right
  • left 一直向右移，直到它指向的数为偶数
  • right 一直向左移，直到它指向的数为奇数
  • 交换 nums[left] 与 nums[right]，并让 left++，right—
  • 重复上述操作，直至 left >= right

对一个数判断奇偶，我们可以使用位运算来优化

  • 如果 num 为奇数，则有：num & 1 = 1
  • 如果 num 为偶数，则有：num & 1 = 0

代码

  1. class Solution {
  2.     public int[] exchange(int[] nums) {
  3.         // 首尾双指针
  4.         int left = 0;
  5.         int right = nums.length - 1;
  6.         while(left < right){
  7.             while(left < right && (nums[left] & 1) != 0){
  8.                 left++;
  9.             }
  10.             while(left < right && (nums[right] & 1) != 1){
  11.                 right--;
  12.             }
  13.             swap(nums,left++,right--);
  14.         }
  15.         return nums;
  16.     }
  18.     private static void swap(int[] nums,int i,int j){
  19.         int tmp = nums[i];
  20.         nums[i] = nums[j];
  21.         nums[j] = tmp;
  22.     }
  23. }

复杂度分析

  • 时间复杂度：O(N)

N 为 nums 数组的长度，时间复杂度为 O(N)

  • 空间复杂度：O(1)

算法中使用了首尾指针 left，right 两个额外变量，空间复杂度为 O(1)