LeetCode 0905「按奇偶排序数组」

我是陈皮，一个在互联网 Coding 的 ITer，个人微信公众号「陈皮的JavaLib」关注第一时间阅读最新技术文章。

题目

给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。返回满足此条件的任一数组作为答案。

示例1：

• 输入：nums = [3,1,2,4]
• 输出：[2,4,3,1]
• 解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。

示例2：

• 输入：nums = [0]
• 输出：[0]

提示：

• 1 <= nums.length <= 5000
• 0 <= nums[i] <= 5000

题目来源：LeetCode

方法一

如果不可以改变原数组的情况，我们可以创建一个新的数组。然后遍历一遍原数组，如果是偶数则放置在新数组的左侧，如果是奇数则放入到新数组的右侧。

时间复杂度为 O(N)，空间复杂度为 O(N)。

package com.chenpi.no0905SortArrayByParity;

import java.util.Arrays;

/**
 * @author 陈皮
 * @version 1.0
 * @description
 * @date 2022/4/28
 */
public class No0905SortArrayByParity {

  public static void main(String[] args) {
    No0905SortArrayByParity inst = new No0905SortArrayByParity();
    int[] nums = {3, 1, 2, 4};
    System.out.println(Arrays.toString(inst.sortArrayByParity(nums)));
  }

  public int[] sortArrayByParity(int[] nums) {

    // 左指针
    int lIndex = 0;
    // 右指针
    int rIndex = nums.length - 1;
    // 新数组
    int[] result = new int[nums.length];

    for (int num : nums) {
      if (num % 2 == 0) {
        result[lIndex++] = num;
      } else {
        result[rIndex--] = num;
      }
    }

    return result;
  }
}

// 输出结果如下
[2, 4, 1, 3]

方法二

如果可以改变原数组的情况下，我们可以采用原地交换的方式，即利用原数组。通过双指针，左指针向后遍历，如果当前元素是偶数，左指针继续向后移动，直到是奇数。右指针向前遍历，如果当前元素是奇数，右指针继续向前移动，直到是偶数。如果这两个指针的位置奇数在偶数前面，则进行数据交换，然后继续遍历。

遍历的过程中，注意数组下标越界问题。

时间复杂度为 O(N)，空间复杂度为 O(1)。

package com.chenpi.no0905SortArrayByParity;

import java.util.Arrays;

/**
 * @author 陈皮
 * @version 1.0
 * @description
 * @date 2022/4/28
 */
public class No0905SortArrayByParity {

  public static void main(String[] args) {
    No0905SortArrayByParity inst = new No0905SortArrayByParity();
    int[] nums = {3, 1, 2, 4};
    System.out.println(Arrays.toString(inst.sortArrayByParity(nums)));
  }

  public int[] sortArrayByParity(int[] nums) {

    // 左指针
    int lIndex = 0;
    // 右指针
    int rIndex = nums.length - 1;

    while (true) {
      // 如果当前元素是偶数，左指针继续向后移动，直到是奇数
      while (lIndex < nums.length && nums[lIndex] % 2 == 0) {
        lIndex++;
      }
      // 如果当前元素是奇数，右指针继续向前移动，直到是偶数
      while (rIndex >= 0 && nums[rIndex] % 2 != 0) {
        rIndex--;
      }
      // 如果还有奇数在偶数前面，则进行交换
      if (lIndex < rIndex) {
        int temp = nums[lIndex];
        nums[lIndex] = nums[rIndex];
        nums[rIndex] = temp;
        continue;
      }
      break;
    }
    return nums;
  }
}

// 输出结果如下
[2, 4, 1, 3]

Leetcode 执行结果：

本次分享到此结束啦~~

如果觉得文章对你有帮助，点赞、收藏、关注、评论，您的支持就是我创作最大的动力！