leetcode 922. Sort Array By Parity II

问题来自 leetcode 922. Sort Array By Parity II

---

和leetcode 905. Sort Array By Parity类似，只是判断条件变了

---

但可惜，下面的代码是错的，错误在于当left < right的时候，有可能这个时候A[left]是偶数，left是奇数，A[right]也是偶数，right也是奇数，这个时候做交换是错误的

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int size = A.size();
        
        int left = 0, right = size - 1;
        while(left < right) {
            
            while(left < right && isValid(A[left], left))
                ++left;
            
            while(left < right && isValid(A[right], right))
                --right;
            
            if (left < right) {
                int tmp = A[left];
                A[left] = A[right];
                A[right] = tmp;
            }     
            ++left;
            --right;
        }
        
        return A;
    }
    
    bool isValid(int val, int index) {
        return val%2 == index%2;
    }
};

---

正确的代码

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int size = A.size();
        
        int pos = 0;
        while(pos < size) {
            
            while(pos < size && isValid(A[pos], pos))                 
                ++pos;                          

            if (pos >= size)
                break;
            
            int next = pos + 1;
            if (pos % 2 == 0) {
                while(true) {
                    while(next < size && isValid(A[next], next))                         ++next;                     if (next >= size) // this shouldn't happen if input is valid
                        return A;

                    // We don't need to check (next < size) again
                    // if the input is valid
                    if (A[next]%2 == 0) {
                        int tmp = A[pos];
                        A[pos] = A[next];
                        A[next] = tmp;
                        break;
                    } else {
                        ++next;
                    }
                }
            } else {
                while(true) {
                    while(next < size && isValid(A[next], next))                         ++next;                     if (next >= size) // this shouldn't happen if input is valid
                        return A;

                    // We don't need to check (next < size) again
                    // if the input is valid
                    if (A[next]%2 == 1) {
                        int tmp = A[pos];
                        A[pos] = A[next];
                        A[next] = tmp;
                        break;
                    } else {
                        ++next;
                    }
                }
            }
            
            // Above if/else will make A[pos] valid, now go 
            // to the next element.
            ++pos;
        }
        
        return A;
    }
    
    bool isValid(int val, int index) {
        return val%2 == index%2;
    }
};