922. Sort Array By Parity II.md

922. Sort Array By Parity II

---

leetcode-cn Daily Challenge on November 12th, 2020.

---

Difficulty : Easy

Related Topics : Array、Sort

---

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Note:

• 2 <= A.length <= 20000
• A.length % 2 == 0
• 0 <= A[i] <= 1000

---

Solution

• mine
  • Java
    • Runtime: 2 ms, faster than 99.67%, Memory Usage: 40.9 MB, less than 85.16% of Java online submissions

      //O(N)time
      //O(1)space
      public int[] sortArrayByParityII(int[] A) {
          int n = A.length;
          int even = 0;
          for (int i = 1; i < n; i += 2) {
              if (A[i] % 2 == 0) {
                  while(even < n){
                      if(A[even] % 2 == 0){
                          even += 2;
                      }else{
                          break;
                      }
                  }
                  swap(A, i, even);
              }
          }
          return A;
      }
      
      void swap(int[] A, int i, int j) {
          if (i == j) return;
          int t = A[i];
          A[i] = A[j];
          A[j] = t;
      }
      

---