题解 | #牛的品种排序I# 双指针

知识点

双指针

思路

维护两个指针，i在左边，j在右边，i从左到右遍历，当遇到i指向的位置是1的时候，j向左移动找到最近的0，然后交换，如果i和j相遇则表示完成。

时间复杂度

双指针，每个节点只会访问常数次，时间复杂度为

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型vector 
     * @return int整型vector
     */
    vector<int> sortCows(vector<int>& cows) {
        int n = cows.size();
        for (int i = 0, j = n - 1; i <= j; i ++) {
            if (!cows[i]) continue;
            while (j >= i and cows[j] == 1) j --;
            if (i < j and cows[j] == 0) {
                swap(cows[i], cows[j]);
                j --;
            }
        }
        return cows;
    }
};