题解 | #牛群的编号重排#
牛群的编号重排
https://www.nowcoder.com/practice/220a216469c14a52b4eb6709e041feb1
考察的知识点：数组；
解答方法分析：
- 使用两个指针，从右向左遍历数组，找到第一个非降序排列的元素
cows[index]。它右边的元素都是降序排列。 - 如果找到了非降序排列的元素，再次使用一个指针，从右向左遍历数组，找到第一个比
cows[index]小的元素cows]。 - 交换
cows[index]和cows[j]。 - 再将
cows[index]右边的元素进行反向，以确保得到的排列是下一个较大的排序。 - 如果没有找到非降序排列的元素，说明当前排序已经是最大的排列，将整个数组进行反转即可，得到最小排列。
所用编程语言：C++；
完整编程代码：↓
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param cows int整型vector
* @return int整型vector
*/
vector<int> nextPermutation(vector<int>& cows) {
int index = cows.size() - 2;
while (index >= 0 && cows[index] <= cows[index + 1]) {
index--;
}
if (index >= 0) {
int j = cows.size() - 1;
while (j >= 0 && cows[index] <= cows[j]) {
j--;
}
int temp = cows[index];
cows[index] = cows[j];
cows[j] = temp;
}
index++;
int right = cows.size() - 1;
while (index < right) {
int temp = cows[index];
cows[index] = cows[right];
cows[right] = temp;
index++;
right--;
}
return cows;
}
};
CVTE公司福利 353人发布
查看21道真题和解析
投递小米集团等公司10个岗位 >