Java

  • /**
    
     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
    
     */
    public class Sort_Array_By_Parity_II {
        class Solution {
            public int[] sortArrayByParityII(int[] A) {
                int j = 1;
                for (int i = 0; i < A.length; i += 2)
                    if (A[i] % 2 == 1) {
    
                        // find next odd-value index
                        while (A[j] % 2 == 1) {
                            j += 2;
                        }
    
                        // Swap A[i] and A[j]
                        int tmp = A[i];
                        A[i] = A[j];
                        A[j] = tmp;
                    }
    
                return A;
            }
        } }
    
  • // OJ: https://leetcode.com/problems/sort-array-by-parity-ii/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        vector<int> sortArrayByParityII(vector<int>& A) {
            for (int i = 0, j = 1, N = A.size(); i < N && j < N; i += 2, j += 2) {
                while (i < N && A[i] % 2 == 0) i += 2;
                while (j < N && A[j] % 2 != 0) j += 2;
                if (i < N) swap(A[i], A[j]);
            }
            return A;
        }
    };
    
  • class Solution(object):
        def sortArrayByParityII(self, A):
            """
            :type A: List[int]
            :rtype: List[int]
            """
            odd = [x for x in A if x % 2 == 1]
            even = [x for x in A if x % 2 == 0]
            res = []
            iseven = True
            while odd or even:
                if iseven:
                    res.append(even.pop())
                else:
                    res.append(odd.pop())
                iseven = not iseven
            return res
    

Java

  • class Solution {
        public int[] sortArrayByParityII(int[] A) {
            int length = A.length;
            int[] sorted = new int[length];
            int evenIndex = 0, oddIndex = 1;
            for (int i = 0; i < length; i++) {
                int num = A[i];
                if (num % 2 == 0) {
                    sorted[evenIndex] = num;
                    evenIndex += 2;
                } else {
                    sorted[oddIndex] = num;
                    oddIndex += 2;
                }
            }
            return sorted;
        }
    }
    
  • // OJ: https://leetcode.com/problems/sort-array-by-parity-ii/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        vector<int> sortArrayByParityII(vector<int>& A) {
            for (int i = 0, j = 1, N = A.size(); i < N && j < N; i += 2, j += 2) {
                while (i < N && A[i] % 2 == 0) i += 2;
                while (j < N && A[j] % 2 != 0) j += 2;
                if (i < N) swap(A[i], A[j]);
            }
            return A;
        }
    };
    
  • class Solution(object):
        def sortArrayByParityII(self, A):
            """
            :type A: List[int]
            :rtype: List[int]
            """
            odd = [x for x in A if x % 2 == 1]
            even = [x for x in A if x % 2 == 0]
            res = []
            iseven = True
            while odd or even:
                if iseven:
                    res.append(even.pop())
                else:
                    res.append(odd.pop())
                iseven = not iseven
            return res
    

All Problems

All Solutions