1. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

  1. 示例：
  3. 输入：nums = [1,2,3,4]
  4. 输出：[1,3,2,4] 
  5. 注：[3,1,2,4] 也是正确的答案之一。

思路：

  • 考虑使用双指针：
    • 1号指针指向第一个偶数（遍历查找，直到找到第一个偶数，如果没有则直接返回原数组即可）
    • 2号指针保持在1号指针之后，并且进行扫描，找到1号指针所指位置后的第一个奇数
class Solution {
    public int[] exchange(int[] nums) {
        int left = -1;
        int right = -1;
        // 找到第一个偶数
        for(int i=0;i<nums.length;i++){
            if(nums[i]%2==0){
                left = i;
                right = i+1;
                break;
            }
        }
        while(right!=-1 && right<nums.length){
            if(nums[right]%2==1){
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                for(int i=left+1;i<nums.length;i++){
                    if(nums[i]%2==0){
                        left = i;
                        right = i+1;
                        break;
                    } 
                }
            }else{
                right++;
            }
        }
        return nums;
    }
}
  • 能够解决问题， 并且也可以使用递归来解决，但是结果太慢，完全无法满足要求。

image.png

  • 优秀解法
    • 使用位运算（加快计算操作）
    • 减少不必要的判断（需要理清理清指针指向以及交换逻辑）
      class Solution {
public int[] exchange(int[] nums) {
   int left = 0;
   int right = 0;
   // 定位到第一个偶数————目的是防止数组前部分奇数过长，导致需要多次进行不必要的交换赋值操作
   for(int i=0;i<nums.length;i++){
       if((nums[left]&1)==0){
           left = i;
           right = i+1;
           break;
       }
   }     
   while(right<nums.length){
       if((nums[right]&1)==1){
           int temp = nums[right];
           nums[right] = nums[left];
           nums[left] = temp;
           left++;
       }
       right++;
   }
   return nums;
}
}