算法题按奇偶排序数组-程序员充电站

905. 按奇偶排序数组

问题描述

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

示例：

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

算法思路

双指针原地交换：

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

额外数组：

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

代码实现

方法一：双指针原地交换

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]

双指针：

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

额外数组：

创建结果数组result = [0,0,0,0]
第一次遍历找偶数：2,4→result = [2,4,0,0]
第二次遍历找奇数：3,1→result = [2,4,3,1]
返回[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] 或其他有效答案}