31. Next Permutation
1.問題

2.想法
提問
題意: 得到下一個更大的排序, 但盡可能較小
function header, parameter
test input
說明想法
由於最大的排序是descending, 因此必須要找出從最高位起第一個ascending的位數, 並從此位數的右方中挑出大於該位數又最接近該位數的數值swap, 並且作ascending排序
測試計算複雜度
3.程式碼
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int index = nums.size() - 1;
while (index >0 &&
nums[index] >= nums[index - 1]) {
index--;
}
if (index == 0) {
sort(nums.begin(), nums.end());
return;
}
int minVal = INT_MAX, minIndex = 0;
for (int i = nums.size() - 1; i >= index -1; i--) {
if (nums[i] > nums[index - 1] &&
minVal > nums[i] ){
minVal = nums[i];
minIndex = i;
}
}
int tmp = nums[index - 1];
nums[index - 1] = nums[minIndex];
nums[minIndex] = tmp;
sort(nums.begin() + index, nums.end());
}
};
Last updated