算法题 按奇偶排序数组 II

922. 按奇偶排序数组 II

问题描述

给定一个非负整数数组nums，其中一半整数是奇数，另一半是偶数。

你需要对数组进行重排序，使得对于所有偶数索引i，nums[i]是偶数；对于所有奇数索引i，nums[i]是奇数。

返回满足条件的任意一种重排序结果。

示例：

输入: nums = [4,2,5,7] 输出: [4,5,2,7] 解释: - 索引0（偶数）: 4（偶数） - 索引1（奇数）: 5（奇数） - 索引2（偶数）: 2（偶数） - 索引3（奇数）: 7（奇数） 其他有效答案包括: [4,7,2,5], [2,5,4,7], [2,7,4,5]

算法思路

双指针：

1. 使用两个指针：
   • even指针从索引0开始，每次移动2步（只检查偶数位置）
   • odd指针从索引1开始，每次移动2步（只检查奇数位置）
2. 遍历偶数位置：
   • 如果nums[even]是奇数，说明放错了位置
   • 在奇数位置中找到一个偶数（即nums[odd]是偶数）
   • 交换这两个元素

额外数组：

1. 创建两个列表分别存储偶数和奇数
2. 按照索引的奇偶性依次从对应列表中取值填充结果数组

代码实现

方法一：双指针原地交换

classSolution{/** * 按奇偶排序数组 II - 双指针原地交换 * * @param nums 输入数组，包含等量的奇数和偶数 * @return 重排序后的数组，偶数索引放偶数，奇数索引放奇数 */publicint[]sortArrayByParityII(int[]nums){intn=nums.length;inteven=0;// 偶数索引指针，从0开始intodd=1;// 奇数索引指针，从1开始// 遍历所有偶数位置while(even<n){// 如果偶数位置放的是奇数if(nums[even]%2==1){// 在奇数位置中找到一个偶数while(nums[odd]%2==1){odd+=2;// 跳到下一个奇数位置}// 交换偶数位置的奇数和奇数位置的偶数swap(nums,even,odd);}even+=2;// 移动到下一个偶数位置}returnnums;}/** * 交换数组中两个位置的元素 */privatevoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}}

方法二：优化双指针

classSolution{/** * 优化：同时移动两个指针 */publicint[]sortArrayByParityII(int[]nums){intn=nums.length;inteven=0;intodd=1;while(even<n&&odd<n){// 找到放错位置的偶数索引（应该是偶数但放了奇数）while(even<n&&nums[even]%2==0){even+=2;}// 找到放错位置的奇数索引（应该是奇数但放了偶数）while(odd<n&&nums[odd]%2==1){odd+=2;}// 如果两个指针都有效，交换它们if(even<n&&odd<n){swap(nums,even,odd);even+=2;odd+=2;}}returnnums;}privatevoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}}

方法三：额外数组

classSolution{/** * 额外数组：使用两个列表分别存储偶数和奇数 */publicint[]sortArrayByParityII(int[]nums){List<Integer>evens=newArrayList<>();List<Integer>odds=newArrayList<>();// 分离偶数和奇数for(intnum:nums){if(num%2==0){evens.add(num);}else{odds.add(num);}}// 按照索引奇偶性重新填充int[]result=newint[nums.length];intevenIndex=0,oddIndex=0;for(inti=0;i<nums.length;i++){if(i%2==0){result[i]=evens.get(evenIndex++);}else{result[i]=odds.get(oddIndex++);}}returnresult;}}

方法四：一次遍历填充

classSolution{/** * 一次遍历填充：直接计算每个元素应该放的位置 */publicint[]sortArrayByParityII(int[]nums){intn=nums.length;int[]result=newint[n];intevenPos=0;// 下一个偶数应该放的位置intoddPos=1;// 下一个奇数应该放的位置for(intnum:nums){if(num%2==0){result[evenPos]=num;evenPos+=2;}else{result[oddPos]=num;oddPos+=2;}}returnresult;}}

算法分析

方法	时间复杂度	空间复杂度
双指针原地交换	O(n)	O(1)
优化双指针	O(n)	O(1)
额外数组	O(n)	O(n)
一次遍历填充	O(n)	O(n)

算法过程

输入：nums = [4,2,5,7]

方法一：

1. 初始：even=0,odd=1,nums=[4,2,5,7]
2. even=0:nums[0]=4（偶数），even=2
3. even=2:nums[2]=5（奇数）
   • 查找奇数位置的偶数：odd=1,nums[1]=2（偶数）
   • 交换nums[2]和nums[1]→nums=[4,5,2,7]
   • even=4（超出范围），结束
4. 返回[4,5,2,7]

输入：nums = [2,3]

1. even=0:nums[0]=2（偶数），even=2
2. 结束，返回[2,3]

输入：nums = [3,2]

1. even=0:nums[0]=3（奇数）
   • odd=1:nums[1]=2（偶数）
   • 交换 →nums=[2,3]
2. 返回[2,3]

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[]nums1={4,2,5,7};int[]result1=solution.sortArrayByParityII(nums1.clone());System.out.println("Test 1: "+Arrays.toString(result1));// [4,5,2,7] 或其他有效答案// 测试用例2：已经正确排序int[]nums2={2,1,4,3};int[]result2=solution.sortArrayByParityII(nums2.clone());System.out.println("Test 2: "+Arrays.toString(result2));// [2,1,4,3]// 测试用例3：完全逆序int[]nums3={1,0,3,2};int[]result3=solution.sortArrayByParityII(nums3.clone());System.out.println("Test 3: "+Arrays.toString(result3));// [0,1,2,3] 或其他有效答案// 测试用例4：两元素int[]nums4={2,3};int[]result4=solution.sortArrayByParityII(nums4.clone());System.out.println("Test 4: "+Arrays.toString(result4));// [2,3]int[]nums5={3,2};int[]result5=solution.sortArrayByParityII(nums5.clone());System.out.println("Test 5: "+Arrays.toString(result5));// [2,3]// 测试用例6：大数组int[]nums6={1,2,3,4,5,6,7,8};int[]result6=solution.sortArrayByParityII(nums6.clone());// 验证结果的正确性booleanvalid6=true;for(inti=0;i<result6.length;i++){if(i%2==0&&result6[i]%2!=0)valid6=false;if(i%2==1&&result6[i]%2!=1)valid6=false;}System.out.println("Test 6"+valid6);// true// 测试用例7：全偶数在前int[]nums7={2,4,6,8,1,3,5,7};int[]result7=solution.sortArrayByParityII(nums7.clone());booleanvalid7=true;for(inti=0;i<result7.length;i++){if(i%2==0&&result7[i]%2!=0)valid7=false;if(i%2==1&&result7[i]%2!=1)valid7=false;}System.out.println("Test 7:"+valid7);// true// 测试用例8：包含0int[]nums8={0,1,2,3};int[]result8=solution.sortArrayByParityII(nums8.clone());System.out.println("Test 8: "+Arrays.toString(result8));// [0,1,2,3] 或其他有效答案}

关键点

1. 双指针：

   • 偶数指针只关注偶数位置
   • 奇数指针只关注奇数位置
   • 当发现错位时，必然能在对方的位置找到可交换的元素

2. 原地操作：

   • 空间复杂度为O(1)
   • 不需要额外的存储空间

常见问题

1. 为什么双指针不会出现死循环？
   • 奇数和偶数数量相等
   • 每次交换都会修复两个错位的位置
   • 最多需要n/2次交换就能完成