java辅助数组、双指针

调整数组中奇数和偶数的位置，使得奇数在前，且奇数之间和偶数之间的相对位置不变

解法一辅助数组

• 用两个数组分别记录数组中的奇数和偶数
• 将奇偶数组中的元素分别填充进原数组

public void reOrderArray(int [] array) {
        List<Integer> odd = new ArrayList<>();
        List<Integer> even = new ArrayList<>();
        for(int a: array){
            if(a % 2 == 0){
                even.add(a);
            }else{
                odd.add(a);
            }
        }
        int index = 0;
        for(int num: odd){
            array[index++] = num;
        }
        for(int num: even){
            array[index++] = num;
        }
    }

解法二：双指针

• 双指针了l，r分别记录替换的左偶数与右奇数的位置

• 每次遇到需要交换的情况，采用移位操作置换，中间元素相对位置不变，前后元素发生交换

  public void reOrderArray(int [] array) {
        int l = 0, r = l;
        while(r < array.length){
            if(array[l] % 2 == 1){
                ++l;
            }else{
                if(array[r] % 2 == 1){
                    resetNum(array, l, r);
                    ++l;
                }
            }
            ++r;
        }
    }
  
    public void resetNum(int[] array, int i, int j){
        int tmp = array[j];
        for(int k = j; k > i; --k){
            array[k] = array[k - 1];
        }
        array[i] = tmp;
    }