题解 | #牛的品种排序II#
牛的品种排序II
https://www.nowcoder.com/practice/43e49fbb98b4497ba46e185918188b1c
考察的知识点:数组、双指针;
解答方法分析:
- 定义三个指针,
left
、cur
和right
,分别代表下一个该放置黑牛、牛和黄牛的位置。 - 初始化
left
为0,right
为数组最后一个位置。 - 通过遍历
cur
指针,根据当前遍历到的牛的类进行判断和操作。 - 如果是黑牛,将当前牛与
left
指向的位置交换,并将left
和cur
针都向右移动步。 - 如果是白牛,直将
cur
指针向右移动一步。 - 如果是黄牛,将当前牛与
right
指向的位置交换,并将right
指针向左移动一步。 - 重复步骤3~6直到
cur
指针遍历完所有牛的种类。 - 返回过排序后的牛。
所用编程语言:C++;
完整编程代码:↓
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param cows int整型vector * @return int整型vector */ vector<int> sortCows(vector<int>& cows) { int n = cows.size(); int left = 0; int right = n - 1; int cur = 0; while (cur <= right) { if (cows[cur] == 0) { swap(cows[left], cows[cur]); left++; cur++; } else if (cows[cur] == 1) { cur++; } else { swap(cows[right], cows[cur]); right--; } } return cows; } };