剑指offer-68、调整数组顺序使奇数位于偶数前⾯(⼆)
<h2 id="题描述">题⽬描述</h2><p>输⼊⼀个⻓度为 n 整数数组，数组⾥⾯可能含有相同的元素，实现⼀个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前⾯部分，所有的偶数位于数组的后⾯部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。</p>
<p>数据范围：0 ≤ n ≤ 50000，数组中每个数的值 0 ≤ val ≤ 10000</p>
<p>要求：时间复杂度 O(n)，空间复杂度 O(1)</p>
<p>示例 1<br>
输⼊：<br>
返回值：<br>
说明：或者也是正确答案</p>
<p>示例 2<br>
输⼊：<br>
返回值：<br>
说明：等也是正确答案</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="两次遍历">两次遍历</h3>
<p>第一次遍历收集奇数，第二次遍历收集偶数</p>
<p>这种方法虽然简单易懂，但需要额外空间，不符合题目要求</p>
<pre><code class="language-java">public class Solution {
public int[] reorderArray(int[] nums) {
if (nums == null || nums.length == 0) {
return new int;
}
int[] result = new int;
int index = 0;
// 第一次遍历：收集所有奇数
for (int num : nums) {
if (num % 2 == 1) {
result = num;
}
}
// 第二次遍历：收集所有偶数
for (int num : nums) {
if (num % 2 == 0) {
result = num;
}
}
return result;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n)</li>
<li>空间复杂度：O(n)</li>
</ul>
<h3 id="双指针交换推荐">双指针交换（推荐）</h3>
<p>这道题需要奇数在⼀半，偶数在另外⼀半就可以，并没有要求他们之间的顺序，那么就可以⽤双指针，⼀个指针在左边，⼀个指针在右边，⽐如 1,3,5,6,7 :</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202505251135477.png" alt="" loading="lazy"></p>
<p>左指针往右遍历直到找到偶数，也就是 6 停下来，</p>
<p>右指针往左⾛，直到找到第⼀个奇数，也就是 7 停下来。</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202505251136293.png" alt="" loading="lazy"></p>
<p>两者交换:</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202505251136664.png" alt="" loading="lazy"></p>
<p>左指针继续往右边⾛，两个指针相遇，结束，这个时候其实偶数已经全部在右边了。</p>
<p>这个例⼦⾥⾯只经过⼀次交换，如果是多次交换，那么结束的条件同样也是两个指针相遇。</p>
<pre><code class="language-java">public class Solution {
public int[] reorderArray(int[] nums) {
if (nums == null || nums.length <= 1) {
return nums;
}
int left = 0; // 左指针，从数组开头开始
int right = nums.length - 1; // 右指针，从数组末尾开始
while (left < right) {
// 左指针向右移动，直到找到偶数
while (left < right && nums % 2 == 1) {
left++;
}
// 右指针向左移动，直到找到奇数
while (left < right && nums % 2 == 0) {
right--;
}
// 如果左指针仍在右指针左边，交换奇偶数
if (left < right) {
int temp = nums;
nums = nums;
nums = temp;
left++;
right--;
}
}
return nums;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，每个元素最多被访问一次</li>
<li><strong>空间复杂度</strong>：O(1)，只使用了常数级别的额外空间</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19526066
頁:
[1]