欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode初学——下一个排列

程序员文章站 2024-02-29 08:16:40
...

题目:

 

Leetcode初学——下一个排列

这道题题目不难,但是他给的示例不好,以至于花了较长的时间

下面我给一个普通的例子给大家参考

4,2,0,2,3,2,0  --> 4 2 0 3 0 2 2

下面是图解:

Leetcode初学——下一个排列

我从后往前找,找到一个数比前面某一个位置的数大

这里有两种情况

Leetcode初学——下一个排列

Leetcode初学——下一个排列

这里我们要选择第二种情况,因为这种情况下,所生成的数是最小的

我们将这两个数换一下位置

Leetcode初学——下一个排列

这是生成的最小数么?

不是

我们还要对换位之后的数的后几位进行一个升序排序

Leetcode初学——下一个排列

最终形成这样一个数才算成功

 

附上代码:

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;
                }
            }
        }
    }

}

结果如下:

Leetcode初学——下一个排列

相关标签: Leetcode学习