LeetCode 905. 按奇偶排序數組 - Java

該題原址:​​https://leetcode-cn.com/problems/sort-array-by-parity/​​

問題描述

問題分析

巧妙的方法需要對數組有深入的了解.

正确的思路是利用左右指針來判斷數組兩頭的值是否為奇數或偶數,在進行相應操作後,移動左右指針,當左右指針相碰則周遊完成.

算法複雜度(O(N/2))

錯誤思路 : 将奇偶分别存放在一個數組中後,之後再按照先添加偶數數組,然後再把奇數數組添加進去傳回該數組即可. 與上面的想法相比,效率太低了,不僅需要周遊整個數組,還需要在把兩個數組的值在重新添加到一個新的數組!

算法複雜度(O(N))

代碼示範

1. 左右指針解法(摘自:​​https://leetcode-cn.com/crzzm/​​)

/**
   * 執行用時 : 3 ms, 在Sort Array By Parity的Java送出中擊敗了98.43% 的使用者
     *記憶體消耗 : 43.6 MB, 在Sort Array By Parity的Java送出中擊敗了78.03% 的使用者
   * 
   */
  public int[] sortArrayByParity1(int[] A) {
    int i = 0;
    int j = A.length - 1;
    int[] B = new int[A.length];
    for (int x = 0; x < A.length; x++) {
      if (A[x] % 2 == 0) {
        B[i] = A[x];
        i++;
      } else {
        B[j] = A[x];
        j--;
      }
    }
    return B;
  }      

2. 雙指針解法(摘自:​​https://leetcode-cn.com/kico/​​)

/**
    *執行用時 : 3 ms, 在Sort Array By Parity的Java送出中擊敗了98.43% 的使用者
    *記憶體消耗 : 37.6 MB, 在Sort Array By Parity的Java送出中擊敗了98.33% 的使用者
    */
    public int[] sortArrayByParity(int[] A) {
        if(A == null || A.length == 1)
            return A;
        //左、右指針初始化
        int left = 0;
        int right = A.length - 1;
        int tem;
        while(left < right){
            //左指針對應奇數值，右指針對應偶數值，進行交換
            if((A[left] & 1) == 1 && (A[right] & 1) == 0){
                tem = A[left];
                A[left] = A[right];
                A[right] = tem;
            }else if((A[left] & 1) == 0){
                //左指針對應的是偶數值，符合題意，繼續向右移動
                left++;
            }
            else if((A[right] & 1) == 1){
                //右指針對應的是奇數值，符合題意，繼續向左移動
                right--;
            }
        }
        return A;
    }      

3.首先想出的笨方法(考慮到雙指針了,但是從沒實作過,感覺太難就沒有深入思考直接用最菜的方法)

class Solution {
  /**
   * 執行用時 : 14 ms, 在Sort Array By Parity的Java送出中擊敗了53.24% 的使用者
     *記憶體消耗 : 40.2 MB, 在Sort Array By Parity的Java送出中擊敗了89.33% 的使用者
   */
    public static int[] sortArrayByParity(int[] A) {
    if (A == null || A.length == 1) {
      return A;
    }
    StringBuilder evenNum = new StringBuilder();
    StringBuilder oddNum = new StringBuilder();
    int[] arr = new int[A.length];
    for (int i : A) {
      if (i % 2 != 0) {
        oddNum.append(i);
        oddNum.append(",");
      } else {
        evenNum.append(i);
        evenNum.append(",");
      }
    }
    if (evenNum.length() == 0 || oddNum.length() == 0) { // 判斷A數組中是否全為偶數或全為奇數
      return A;
    }
    String[] strEven = evenNum.toString().split(",");
    String[] strOdd = oddNum.toString().split(",");
    for (int i = 0; i < arr.length; i++) {
      if (i < strEven.length) {
        arr[i] = Integer.valueOf(strEven[i]); // 先将strEven數組的各個元素轉換為int類型添加到arr數組中
      }
      if (i >= strEven.length) {
        arr[i] = Integer.valueOf(strOdd[i - strEven.length]); // 之後就把奇數添加到arr數組中
      }
    }
    return arr;
  }
}      

總結