登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 安全 ›剑指offer-13、调整数组顺序使奇数位于偶数前面（一） ...

剑指offer-13、调整数组顺序使奇数位于偶数前面（一）

翁谌缜 5 天前
题⽬描述

输⼊⼀个⻓度为 n 整数数组，数组⾥⾯不含有相同的元素，实现⼀个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前⾯部分，所有的偶数位于数组的后⾯部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
示例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]
思路及解答

空间换时间（辅助数组）

通过创建两个临时数组分别存储奇数和偶数，然后合并它们。这种方法简单易懂，但需要额外的空间。
新建⼀个数组， copy ⼀份，先计算出奇数的个数，也就是能够知道第⼀个偶数应该放在数组的哪⼀个位置，然后再遍历⼀次，依次放到对应的位置即可。
  1. public int[] reorderArray(int[] nums) {
  2.     if (nums == null || nums.length == 0) {
  3.         return nums;
  4.     }
  5.    
  6.     // 使用ArrayList动态存储，避免预先计算大小
  7.     List<Integer> oddList = new ArrayList<>();
  8.     List<Integer> evenList = new ArrayList<>();
  9.    
  10.     // 第一次遍历：分离奇偶数
  11.     for (int num : nums) {
  12.         if (num % 2 != 0) {
  13.             oddList.add(num);
  14.         } else {
  15.             evenList.add(num);
  16.         }
  17.     }
  18.    
  19.     // 合并结果
  20.     int[] result = new int[nums.length];
  21.     int index = 0;
  22.     for (int odd : oddList) {
  23.         result[index++] = odd;
  24.     }
  25.     for (int even : evenList) {
  26.         result[index++] = even;
  27.     }
  28.    
  29.     return result;
  30. }
复制代码

  • ​时间复杂度​：O(n)，需要遍历数组两次（分离和合并各一次）
  • ​空间复杂度​：O(n)，需要额外的两个列表存储所有元素
双指针原地排序（类似插入排序）

使用类似插入排序的思想，维护一个"已排序奇数"的边界，当遇到奇数时，将其插入到边界位置并移动边界。这种方法不需要额外空间，但时间复杂度较高。
  1. public int[] reorderArray(int[] nums) {
  2.     if (nums == null || nums.length == 0) {
  3.         return nums;
  4.     }
  5.    
  6.     int oddBoundary = 0; // 奇数边界
  7.     for (int i = 0; i < nums.length; i++) {
  8.         if (nums[i] % 2 != 0) {
  9.             // 从i位置向前移动到oddBoundary位置
  10.             int temp = nums[i];
  11.             // 将[i-1, oddBoundary]区间元素后移一位
  12.             for (int j = i - 1; j >= oddBoundary; j--) {
  13.                 nums[j + 1] = nums[j];
  14.             }
  15.             nums[oddBoundary] = temp;
  16.             oddBoundary++;
  17.         }
  18.     }
  19.    
  20.     return nums;
  21. }
复制代码

  • ​时间复杂度​：O(n²)，最坏情况下每次奇数都需要移动大量元素
  • ​空间复杂度​：O(1)，原地排序，不需要额外空间
两次遍历填充法

通过两次遍历数组，第一次填充所有奇数，第二次填充所有偶数。这种方法结合了方法一的思路，但使用固定大小的结果数组
  1. public int[] reorderArray(int[] nums) {
  2.     if (nums == null || nums.length == 0) {
  3.         return nums;
  4.     }
  5.    
  6.     int[] result = new int[nums.length];
  7.     int index = 0;
  8.    
  9.     // 第一次遍历：填充奇数
  10.     for (int num : nums) {
  11.         if (num % 2 != 0) {
  12.             result[index++] = num;
  13.         }
  14.     }
  15.    
  16.     // 第二次遍历：填充偶数
  17.     for (int num : nums) {
  18.         if (num % 2 == 0) {
  19.             result[index++] = num;
  20.         }
  21.     }
  22.    
  23.     return result;
  24. }
复制代码

  • 时间复杂度​：O(n)，需要遍历数组两次
  • ​空间复杂度​：O(n)，需要一个结果数组
稳定的双指针交换法

使用两个指针，一个从前往后找偶数，一个从后往前找奇数，然后交换它们的位置。这种方法需要特别注意保持相对顺序
  1. public int[] reorderArray(int[] nums) {
  2.     if (nums == null || nums.length == 0) {
  3.         return nums;
  4.     }
  5.    
  6.     int left = 0, right = nums.length - 1;
  7.    
  8.     while (left < right) {
  9.         // 从左找第一个偶数
  10.         while (left < right && nums[left] % 2 != 0) {
  11.             left++;
  12.         }
  13.         // 从右找第一个奇数
  14.         while (left < right && nums[right] % 2 == 0) {
  15.             right--;
  16.         }
  17.         
  18.         if (left < right) {
  19.             // 交换并保持相对顺序
  20.             int temp = nums[left];
  21.             // 将[left+1, right]区间元素前移一位
  22.             for (int i = left + 1; i <= right; i++) {
  23.                 nums[i - 1] = nums[i];
  24.             }
  25.             nums[right] = temp;
  26.         }
  27.     }
  28.    
  29.     return nums;
  30. }
复制代码

  • 时间复杂度​：O(n²)，最坏情况下需要移动大量元素
  • ​空间复杂度​：O(1)，原地操作
方法对比与总结

方法时间复杂度空间复杂度优点缺点辅助数组法O(n)O(n)实现简单，顺序有保证空间开销大双指针原地排序O(n²)O(1)空间效率高时间效率低两次遍历填充法O(n)O(n)时间效率高空间开销中等稳定双指针交换法O(n²)O(1)空间效率高实现复杂，时间效率低优化双指针法O(n²)O(1)空间效率高，顺序保证好时间效率低
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
翁谌缜
5 天前

0

粉丝关注

13

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫