当前位置：首页 > news >正文

算法的学习笔记—调整数组顺序使奇数位于偶数前面(牛客JZ21)

news 来源：原创 2024/9/20 15:32:29

😀前言
在数据处理和算法问题中，经常需要对数组进行特定的调整或排序。本文将介绍如何调整一个整数数组的顺序，使得所有的奇数位于数组的前半部分，而所有的偶数位于数组的后半部分，并且保持奇数和奇数、偶数和偶数之间的相对顺序不变。

🏠个人主页：尘觉主页

文章目录

😀调整数组顺序使奇数位于偶数前面
- 题目链接
- 😁题目描述
- 😍示例
- - 示例1
  - 示例2
  - 示例3
- 🥰解题思路
- - 💓题思路
  - 💞方法一：使用额外空间
  - - - 💕步骤：
    - ❤️‍🔥代码实现：
  - 💞方法二：原地调整
  - - 💕步骤：
    - ❤️‍🔥代码实现：
    - 分析：
- 😄比较与总结

😀调整数组顺序使奇数位于偶数前面

题目链接

牛客网

😁题目描述

输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

数据范围：0≤n≤5000，数组中每个数的值 0≤val≤10000

要求：时间复杂度 O(n)，空间复杂度 O(n)

进阶：时间复杂度 O(n²)，空间复杂度 O(1)

😍示例

示例1

输入：[1,2,3,4]
返回值：[1,3,2,4]

示例2

输入：[2,4,6,5,7]
返回值：[5,7,2,4,6]

示例3

输入：[1,3,5,6,7]
返回值：[1,3,5,7,6]

需要保证奇数和奇数，偶数和偶数之间的相对位置不变，这和书本不太一样。例如对于 [1,2,3,4,5]，调整后得到 [1,3,5,2,4]，而不能是 {5,1,3,4,2} 这种相对位置改变的结果。

d03a2efa-ef19-4c96-97e8-ff61df8061d3

🥰解题思路

💓题思路

为了解决这个问题，有两种常见的方法：使用额外的空间创建新数组，或在原数组上进行调整。下面将详细介绍这两种方法。

💞方法一：使用额外空间

通过使用额外的空间，可以在O(n)的时间复杂度内完成调整，同时保持原有的相对顺序。

💕步骤：

遍历数组，统计奇数的个数，并创建一个与原数组大小相同的副本。
重新遍历数组，将奇数按顺序放在副本的前半部分，偶数放在副本的后半部分。
将副本中的元素按顺序放回原数组。

❤️‍🔥代码实现：

public int[] reOrderArray (int[] nums) {// 奇数个数int oddCnt = 0;for (int x : nums)if (!isEven(x))oddCnt++;int[] copy = nums.clone();int i = 0, j = oddCnt;for (int num : copy) {if (num % 2 == 1)nums[i++] = num;elsenums[j++] = num;}return nums;
}private boolean isEven(int x) {return x % 2 == 0;
}

分析：

时间复杂度：O(n)，遍历数组两次。
空间复杂度：O(n)，因为需要额外的空间来存储副本。

💞方法二：原地调整

如果对空间复杂度有更高的要求，可以选择在原数组上进行调整。我们可以借助冒泡排序的思想，每次将当前的偶数向后交换，直至它被排到最后一位。

💕步骤：

从右向左遍历数组，每次遇到偶数时，将其与后面的元素交换，直至它后面紧跟的元素为奇数。
重复上述操作，直到所有的偶数都排到数组的右端。

❤️‍🔥代码实现：

public int[] reOrderArray(int[] nums) {int N = nums.length;for (int i = N - 1; i > 0; i--) {for (int j = 0; j < i; j++) {if (isEven(nums[j]) && !isEven(nums[j + 1])) {swap(nums, j, j + 1);}}}return nums;
}private boolean isEven(int x) {return x % 2 == 0;
}private void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;
}