面试常考:如何原地重排数组?这个思路绝了

解题思路

这道题我们用两个指针分别追踪奇数位和偶数位,每次检查最后一个元素是奇数还是偶数,然后把它交换到对应的位置上。

比如最后一个元素是奇数,就把它换到下一个需要填充的奇数位(1, 3, 5…),换过来的元素又成为新的"最后一个元素",继续这个过程。

这样做的优势是不需要额外空间,而且每次交换都在推进进度,最终当奇数位和偶数位都填满后,数组自然就符合要求了。

举个栗子

输入:[4, 2, 5, 7]

执行过程:

1. 初始:[4, 2, 5, 7],最后元素 7(奇数) → 交换到 odd=1 →[4, 7, 5, 2]
2. 最后元素 2(偶数) → 交换到 even=0 →[2, 7, 5, 4]
3. 最后元素 4(偶数) → 交换到 even=2 →[2, 7, 4, 5]
4. 最后元素 5(奇数) → 交换到 odd=3 →[2, 7, 4, 5]

输出:[2, 7, 4, 5]

代码实现

publicstaticint[]sortArrayByParityII(int[]nums){intn=nums.length;for(intodd=1,even=0;odd<n&&even<n;){if((nums[n-1]&1)==1){// 最后一个元素是奇数,放到奇数位swap(nums,odd,n-1);odd+=2;}else{// 最后一个元素是偶数,放到偶数位swap(nums,even,n-1);even+=2;}}returnnums;}publicstaticvoidswap(int[]nums,inti,intj){inttmp=nums[i];nums[i]=nums[j];nums[j]=tmp;}

如果觉得有帮助，欢迎点赞、关注、转发~