剑指offer-13、调整数组顺序使奇数位于偶数前面（一）
<h2 id="题描述">题⽬描述</h2><p>输⼊⼀个⻓度为 n 整数数组，数组⾥⾯不含有相同的元素，实现⼀个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前⾯部分，所有的偶数位于数组的后⾯部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。</p>
<p>示例1<br>
输⼊：<br>
返回值：</p>
<p>示例2<br>
输⼊：<br>
返回值：</p>
<p>示例3<br>
输⼊：<br>
返回值：</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="空间换时间辅助数组">空间换时间（辅助数组）</h3>
<p>通过创建两个临时数组分别存储奇数和偶数，然后合并它们。这种方法简单易懂，但需要额外的空间。</p>
<p>新建⼀个数组， copy ⼀份，先计算出奇数的个数，也就是能够知道第⼀个偶数应该放在数组的哪⼀个位置，然后再遍历⼀次，依次放到对应的位置即可。</p>
<pre><code class="language-java">public int[] reorderArray(int[] nums) {
if (nums == null || nums.length == 0) {
return nums;
}
// 使用ArrayList动态存储，避免预先计算大小
List<Integer> oddList = new ArrayList<>();
List<Integer> evenList = new ArrayList<>();
// 第一次遍历：分离奇偶数
for (int num : nums) {
if (num % 2 != 0) {
oddList.add(num);
} else {
evenList.add(num);
}
}
// 合并结果
int[] result = new int;
int index = 0;
for (int odd : oddList) {
result = odd;
}
for (int even : evenList) {
result = even;
}
return result;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，需要遍历数组两次（分离和合并各一次）</li>
<li><strong>空间复杂度</strong>：O(n)，需要额外的两个列表存储所有元素</li>
</ul>
<h3 id="双指针原地排序类似插入排序">双指针原地排序（类似插入排序）</h3>
<p>使用类似插入排序的思想，维护一个"已排序奇数"的边界，当遇到奇数时，将其插入到边界位置并移动边界。这种方法不需要额外空间，但时间复杂度较高。</p>
<pre><code class="language-java">public int[] reorderArray(int[] nums) {
if (nums == null || nums.length == 0) {
return nums;
}
int oddBoundary = 0; // 奇数边界
for (int i = 0; i < nums.length; i++) {
if (nums % 2 != 0) {
// 从i位置向前移动到oddBoundary位置
int temp = nums;
// 将区间元素后移一位
for (int j = i - 1; j >= oddBoundary; j--) {
nums = nums;
}
nums = temp;
oddBoundary++;
}
}
return nums;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²)，最坏情况下每次奇数都需要移动大量元素</li>
<li><strong>空间复杂度</strong>：O(1)，原地排序，不需要额外空间</li>
</ul>
<h3 id="两次遍历填充法">两次遍历填充法</h3>
<p>通过两次遍历数组，第一次填充所有奇数，第二次填充所有偶数。这种方法结合了方法一的思路，但使用固定大小的结果数组</p>
<pre><code class="language-java">public int[] reorderArray(int[] nums) {
if (nums == null || nums.length == 0) {
return nums;
}
int[] result = new int;
int index = 0;
// 第一次遍历：填充奇数
for (int num : nums) {
if (num % 2 != 0) {
result = num;
}
}
// 第二次遍历：填充偶数
for (int num : nums) {
if (num % 2 == 0) {
result = num;
}
}
return result;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，需要遍历数组两次</li>
<li><strong>空间复杂度</strong>：O(n)，需要一个结果数组</li>
</ul>
<h3 id="稳定的双指针交换法">稳定的双指针交换法</h3>
<p>使用两个指针，一个从前往后找偶数，一个从后往前找奇数，然后交换它们的位置。这种方法需要特别注意保持相对顺序</p>
<pre><code class="language-java">public int[] reorderArray(int[] nums) {
if (nums == null || nums.length == 0) {
return nums;
}
int left = 0, right = nums.length - 1;
while (left < right) {
// 从左找第一个偶数
while (left < right && nums % 2 != 0) {
left++;
}
// 从右找第一个奇数
while (left < right && nums % 2 == 0) {
right--;
}
if (left < right) {
// 交换并保持相对顺序
int temp = nums;
// 将区间元素前移一位
for (int i = left + 1; i <= right; i++) {
nums = nums;
}
nums = temp;
}
}
return nums;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²)，最坏情况下需要移动大量元素</li>
<li><strong>空间复杂度</strong>：O(1)，原地操作</li>
</ul>
<h3 id="优化的双指针法保持稳定性">优化的双指针法（保持稳定性）</h3>
<p>结合双指针和插入排序的思想，维护奇数指针和遍历指针，当遇到奇数时，将其插入到奇数指针位置并移动指针。</p>
<pre><code class="language-java">public int[] reorderArray(int[] nums) {
if (nums == null || nums.length == 0) {
return nums;
}
int oddPos = 0;
for (int i = 0; i < nums.length; i++) {
if (nums % 2 != 0) {
// 记录当前奇数
int temp = nums;
// 将区间元素后移一位
for (int j = i; j > oddPos; j--) {
nums = nums;
}
nums = temp;
oddPos++;
}
}
return nums;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²)，最坏情况下需要移动大量元素</li>
<li><strong>空间复杂度</strong>：O(1)，原地操作</li>
</ul>
<h3 id="方法对比与总结">方法对比与总结</h3>
<table>
<thead>
<tr>
<th>方法</th>
<th>时间复杂度</th>
<th>空间复杂度</th>
<th>优点</th>
<th>缺点</th>
</tr>
</thead>
<tbody>
<tr>
<td>辅助数组法</td>
<td>O(n)</td>
<td>O(n)</td>
<td>实现简单，顺序有保证</td>
<td>空间开销大</td>
</tr>
<tr>
<td>双指针原地排序</td>
<td>O(n²)</td>
<td>O(1)</td>
<td>空间效率高</td>
<td>时间效率低</td>
</tr>
<tr>
<td>两次遍历填充法</td>
<td>O(n)</td>
<td>O(n)</td>
<td>时间效率高</td>
<td>空间开销中等</td>
</tr>
<tr>
<td>稳定双指针交换法</td>
<td>O(n²)</td>
<td>O(1)</td>
<td>空间效率高</td>
<td>实现复杂，时间效率低</td>
</tr>
<tr>
<td>优化双指针法</td>
<td>O(n²)</td>
<td>O(1)</td>
<td>空间效率高，顺序保证好</td>
<td>时间效率低</td>
</tr>
</tbody>
</table>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/18992756
頁:
[1]