Paste_Image.png
My code:
import java.util.Arrays;
public class Solution {
public void nextPermutation(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1)
return;
int i = nums.length - 2;
for (; i >= 0; i--) {
if (nums[i] >= nums[i + 1])
continue;
else {
int diff = Integer.MAX_VALUE;
int minDiffIndex = 0;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] - nums[i] > 0 && nums[j] - nums[i] < diff) {
diff = nums[j] - nums[i];
minDiffIndex = j;
}
}
int temp = nums[minDiffIndex];
nums[minDiffIndex] = nums[i];
nums[i] = temp;
Arrays.sort(nums, i + 1, nums.length);
break;
}
}
if (i < 0)
reverse(nums);
}
private void reverse(int[] nums) {
int[] temp = new int[nums.length];
for (int i = 0; i < nums.length; i++)
temp[i] = nums[nums.length - 1 - i];
nums = temp;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] a = {3, 2, 1};
test.nextPermutation(a);
}
}
My test result:
这次作业有点难。昨天写好了，因为简书的渣网页，登陆不进去，所以只能现在给发上来。
其实这类题， 往往可以举一个复杂点的例子，然后思考下自己的脑子是怎么思考的。
很明显，就是从末尾向头部遍历，如果一直是递增的就不管他，然后如果突然变小，就要把这个小的和之前右侧中，与该值最接近且比他大的值交换，然后将右侧数列重新排序。
最后考虑下如果直接是逆序排列的，只要将它反转即可。推荐一个博客。
http://bangbingsyb.blogspot.com/2014/11/leetcode-next-permutation.html
讲的比我清楚。
**
总结：Array, 在草稿纸上多画画例子，就会有思路了。
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public void nextPermutation(int[] nums) {
if (nums == null || nums.length <= 1)
return;
int change = -1;
/** find the index which should be changed at first */
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
change = i;
break;
}
}
/** if the whole array is arranged reversely, reverse the whole array */
if (change == -1) {
for (int i = 0; i < nums.length / 2; i++) {
int temp = nums[i];
nums[i] = nums[nums.length - 1 - i];
nums[nums.length - 1 - i] = temp;
}
return;
}
/** find the elem which is minimum but bigger than nums[change] */
int min = Integer.MAX_VALUE;
int minIndex = change + 1;
for (int i = nums.length - 1; i > change; i--) {
if (nums[i] < min && nums[i] > nums[change]) {
min = nums[i];
minIndex = i;
}
}
/** swap nums[change] and nums[minIndex] */
int temp = nums[change];
nums[change] = nums[minIndex];
nums[minIndex] = temp;
/** sort the rest array */
Arrays.sort(nums, change + 1, nums.length);
}
}
这次一遍就做出来了。。。进步了很多。主要也是有点印象。
刚投了份实习申请，一个小时后就被拒了。。。
Anyway, Good luck, Richardo!
