算法题 按奇偶排序数组

905. 按奇偶排序数组

问题描述

给定一个非负整数数组nums，返回一个数组，其中所有偶数元素位于所有奇数元素之前。你可以返回满足此条件的任意答案。

示例：

输入: nums = [3,1,2,4] 输出: [2,4,3,1] 解释: 输出 [4,2,3,1], [2,4,1,3] 和 [4,2,1,3] 也会被接受。

算法思路

双指针原地交换：

1. 使用两个指针left和right，分别从数组开头和末尾开始
2. left指针寻找奇数，right指针寻找偶数
3. 当left找到奇数且right找到偶数时，交换两个元素
4. 重复直到两个指针相遇

额外数组：

1. 创建一个新数组用于存储结果
2. 第一次遍历将所有偶数放入新数组
3. 第二次遍历将所有奇数放入新数组
4. 返回新数组

代码实现

方法一：双指针原地交换

classSolution{/** * 按奇偶排序数组 - 双指针原地交换 * * @param nums 输入的非负整数数组 * @return 所有偶数在前，奇数在后的数组 */publicint[]sortArrayByParity(int[]nums){intleft=0;// 左指针，从数组开头开始intright=nums.length-1;// 右指针，从数组末尾开始// 当两个指针相遇时停止while(left<right){// 左指针寻找奇数（偶数就跳过）if(nums[left]%2==0){left++;}// 右指针寻找偶数（奇数就跳过）elseif(nums[right]%2==1){right--;}// 左指针找到奇数，右指针找到偶数，交换它们else{inttemp=nums[left];nums[left]=nums[right];nums[right]=temp;left++;right--;}}returnnums;}}

方法二：额外数组

classSolution{/** * 按奇偶排序数组 - 额外数组 * * @param nums 输入的非负整数数组 * @return 所有偶数在前，奇数在后的数组 */publicint[]sortArrayByParity(int[]nums){int[]result=newint[nums.length];// 创建结果数组intindex=0;// 结果数组的当前填充位置// 第一次遍历：将所有偶数放入结果数组for(intnum:nums){if(num%2==0){result[index++]=num;}}// 第二次遍历：将所有奇数放入结果数组for(intnum:nums){if(num%2==1){result[index++]=num;}}returnresult;}}

算法分析

• 时间复杂度：
  • 双指针：O(n)，每个元素最多被访问一次
  • 额外数组：O(n)，需要遍历数组两次
• 空间复杂度：
  • 双指针：O(1)，原地修改
  • 额外数组：O(n)，需要额外的数组空间

算法过程

输入：nums = [3,1,2,4]

双指针：

1. 初始状态：left=0,right=3,nums=[3,1,2,4]
2. nums[0]=3（奇数），nums[3]=4（偶数）→ 交换 →nums=[4,1,2,3]，left=1,right=2
3. nums[1]=1（奇数），nums[2]=2（偶数）→ 交换 →nums=[4,2,1,3]，left=2,right=1
4. left >= right，循环结束，返回[4,2,1,3]

额外数组：

1. 创建结果数组result = [0,0,0,0]
2. 第一次遍历找偶数：2,4→result = [2,4,0,0]
3. 第二次遍历找奇数：3,1→result = [2,4,3,1]
4. 返回[2,4,3,1]

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[]nums1={3,1,2,4};int[]result1=solution.sortArrayByParity(nums1.clone());System.out.println("Test 1: "+Arrays.toString(result1));// [4,2,1,3] 或其他有效答案// 测试用例2：全偶数int[]nums2={2,4,6,8};int[]result2=solution.sortArrayByParity(nums2.clone());System.out.println("Test 2: "+Arrays.toString(result2));// [2,4,6,8]// 测试用例3：全奇数int[]nums3={1,3,5,7};int[]result3=solution.sortArrayByParity(nums3.clone());System.out.println("Test 3: "+Arrays.toString(result3));// [1,3,5,7]// 测试用例4：单元素int[]nums4={5};int[]result4=solution.sortArrayByParity(nums4.clone());System.out.println("Test 4: "+Arrays.toString(result4));// [5]// 测试用例5：空数组int[]nums5={};int[]result5=solution.sortArrayByParity(nums5.clone());System.out.println("Test 5: "+Arrays.toString(result5));// []// 测试用例6：偶数在前int[]nums6={2,4,1,3};int[]result6=solution.sortArrayByParity(nums6.clone());System.out.println("Test 6: "+Arrays.toString(result6));// [2,4,3,1] 或其他有效答案// 测试用例7：奇数在前int[]nums7={1,3,2,4};int[]result7=solution.sortArrayByParity(nums7.clone());System.out.println("Test 7: "+Arrays.toString(result7));// [4,2,3,1] 或其他有效答案}

关键点

1. 问题：

   • 这是一个分组问题，将数组分为偶数和奇数两组
   • 不需要保持原有顺序，只要满足偶数在前即可

2. 双指针核心思想：

   • 利用两个指针从两端向中间移动
   • 找到"错位"的元素（左边的奇数和右边的偶数）进行交换
   • 保证交换后左边都是偶数，右边都是奇数

3. 边界处理：

   • 空数组和单元素数组的处理
   • 全偶数或全奇数的特殊情况

常见问题

1. 双指针？
   • 每次交换都是将一个偶数移到左边，一个奇数移到右边
   • 当指针相遇时，左边的所有元素都是偶数，右边的所有元素都是奇数