题解 | #牛的品种排序I# 双指针
牛的品种排序I
https://www.nowcoder.com/practice/e3864ed7689d460c9e2da77e1c866dce
知识点
双指针
思路
维护两个指针，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;
}
};
查看4道真题和解析
360集团公司氛围 347人发布
