思路还是清楚的，从后面倒着数，中间有一些问题没考虑到，不过很快解决，少数次过
1 class Solution { 2 public: 3 void nextPermutation(vector<int> &num) { 4 // Start typing your C/C++ solution below 5 // DO NOT write int main() function 6 vector<int> des; 7 int i; 8 for (i = num.size()-1; i > 0; i--) { 9 if (num[i] <= num[i-1]) des.push_back(num[i]); 10 else break; 11 } 12 if (!i) { 13 des.push_back(num[0]); 14 num = des; 15 } 16 else { 17 int tmp = num[i-1]; 18 des.push_back(num[i]); 19 int j; 20 for (j = 0; j < des.size(); j++) 21 if (des[j] > num[i-1]) break; 22 num[i-1] = des[j]; 23 for (int k = 0; k < des.size(); k++) { 24 if (k != j) num[i+k] = des[k]; 25 else num[i+k] = tmp; 26 } 27 } 28 } 29 };
后来写了段更加好的代码
1 class Solution { 2 public: 3 void nextPermutation(vector<int> &num) { 4 // Start typing your C/C++ solution below 5 // DO NOT write int main() function 6 if (!num.size()) return; 7 int pos = num.size(); 8 for (int i = num.size()-1; i >= 0; i--) { 9 if (i && num[i] > num[i-1]) { 10 pos = i; 11 break; 12 } 13 } 14 if (pos == num.size()) { 15 reverse(num.begin(), num.end()); 16 return; 17 } 18 for (int i = num.size()-1; i >= pos; i--) { 19 if (num[i] > num[pos-1]) { 20 swap(num[i], num[pos-1]); 21 break; 22 } 23 } 24 reverse(num.begin()+pos, num.end()); 25 } 26 };
C#, Array.Reverse()函数并不能对一段Array进行Reverse，所以没选择第二段代码
1 public class Solution { 2 public void NextPermutation(int[] nums) { 3 List<int> des = new List<int>(); 4 int i = 0; 5 for (i = nums.Length-1; i > 0; i--) { 6 if (nums[i] <= nums[i-1]) des.Add(nums[i]); 7 else break; 8 } 9 if (i == 0) { 10 des.Add(nums[0]); 11 for (int k = 0; k < des.Count; k++) nums[k] = des[k]; 12 } 13 else { 14 int tmp = nums[i-1]; 15 des.Add(nums[i]); 16 int j = 0; 17 for (j = 0; j < des.Count; j++) { 18 if (des[j] > nums[i-1]) break; 19 } 20 nums[i-1] = des[j]; 21 for (int k = 0; k < des.Count; k++) { 22 if (k != j) nums[i+k] = des[k]; 23 else nums[i+k] = tmp; 24 } 25 } 26 } 27 }