Leetcode初学——下一个排列
程序员文章站
2024-02-29 08:16:40
...
题目:
这道题题目不难,但是他给的示例不好,以至于花了较长的时间
下面我给一个普通的例子给大家参考
4,2,0,2,3,2,0 --> 4 2 0 3 0 2 2
下面是图解:
我从后往前找,找到一个数比前面某一个位置的数大
这里有两种情况
这里我们要选择第二种情况,因为这种情况下,所生成的数是最小的
我们将这两个数换一下位置
这是生成的最小数么?
不是
我们还要对换位之后的数的后几位进行一个升序排序
最终形成这样一个数才算成功
附上代码:
class Solution {
public void nextPermutation(int[] nums) {
int n=nums.length;
int temp=0;
int flag=1;
int i=1,temp_i=i,j=i+1,temp_j=j;
int min=n+1;
for(i=1;i<n;i++){
for(j=i;j<=n;j++){
if(nums[n-j]<nums[n-i]){
flag=0;
if(j<min){
min=j;
temp_i=i;
temp_j=j;
}
break;
}
}
if(j>n) continue;
}
if(flag==0){
temp=nums[n-temp_i];
nums[n-temp_i]=nums[n-temp_j];
nums[n-temp_j]=temp;
bubbleSort(nums,n-temp_j);
}
if(flag==1){
bubbleSort(nums);
}
}
// 冒泡排序
public void bubbleSort(int[] nums, int i ) {
int len = nums.length;
int k=i;
while(i<len) {
for (int j = k+1; j < len -1; j++) {
if (nums[j] > nums[j+1]) { // 相邻元素两两对比
int temp = nums[j+1]; // 元素交换
nums[j+1] = nums[j];
nums[j] = temp;
}
}
i++;
}
}
// 冒泡排序
public void bubbleSort(int[] nums) {
int len = nums.length;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1 - i; j++) {
if (nums[j] > nums[j+1]) { // 相邻元素两两对比
int temp = nums[j+1]; // 元素交换
nums[j+1] = nums[j];
nums[j] = temp;
}
}
}
}
}
结果如下:
上一篇: django实现前后台交互实例