42. 调整数组顺序使奇数位于偶数前面 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不
时间: 2023-12-08 21:20:30 浏览: 45
这个问题可以使用多种方法来解决,以下是其中的两种方法:
方法一:使用辅助数组
1. 定义一个辅助数组 result,用来存储排好序的数组;
2. 遍历原数组,如果当前元素是奇数,则将该元素加入 result 数组的末尾,否则加入 result 数组的开头;
3. 遍历完成后,将 result 数组复制回原数组。
以下是示例代码:
```
void reorderArray(vector<int>& nums) {
vector<int> result;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] % 2 == 1) {
result.push_back(nums[i]);
} else {
result.insert(result.begin(), nums[i]);
}
}
nums = result;
}
```
方法二:使用快慢指针
1. 定义两个指针 i 和 j,分别指向数组的开头和结尾;
2. 当 i 指向的元素是奇数时,继续向后移动 i;
3. 当 j 指向的元素是偶数时,继续向前移动 j;
4. 当 i 和 j 指向的元素分别是偶数和奇数时,交换两个元素的位置;
5. 重复步骤 2-4 直到 i 和 j 相遇。
以下是示例代码:
```
void reorderArray(vector<int>& nums) {
int i = 0, j = nums.size() - 1;
while (i < j) {
while (i < j && nums[i] % 2 == 1) i++;
while (i < j && nums[j] % 2 == 0) j--;
if (i < j) swap(nums[i], nums[j]);
}
}
```
以上两种方法的时间复杂度都是 O(n),但第一种方法需要使用额外的空间,而第二种方法可以原地修改数组。
相关推荐
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)