当前位置：网站首页>leetcode T31:下一排列

leetcode T31:下一排列

2022-07-01 08:17:00 【範謙之】

題目描述

整數數組的一個排列就是將其所有成員以序列或線性順序排列。

例如，arr = [1,2,3] ，以下這些都可以視作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整數數組的下一個排列是指其整數的下一個字典序更大的排列。更正式地，如果數組的所有排列根據其字典順序從小到大排列在一個容器中，那麼數組的下一個排列就是在這個有序容器中排在它後面的那個排列。如果不存在下一個更大的排列，那麼這個數組必須重排為字典序最小的排列（即，其元素按昇序排列）。
例如，arr = [1,2,3] 的下一個排列是 [1,3,2] 。
類似地，arr = [2,3,1] 的下一個排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一個排列是 [1,2,3] ，因為 [3,2,1] 不存在一個字典序更大的排列。

給你一個整數數組 nums ，找出 nums 的下一個排列。必須原地修改，只允許使用額外常數空間。

示例 1：

輸入：nums = [1,2,3]
輸出：[1,3,2]

示例 2：

輸入：nums = [3,2,1]
輸出：[1,2,3]

示例 3：

輸入：nums = [1,1,5]
輸出：[1,5,1]

提示

1 <= nums.length <= 100
0 <= nums[i] <= 100

思路

首先從右往左找，找到一個下標 $i n d$ ，使其右邊所有數都是降序排列。例如 :

↓
1432, ind=0

隨後，在 $[i n d + 1, n u m s . l e n g t h - 1]$ 的書中選取一個最小的且大於 $a [i n d]$ 的數，與 $a [i n d]$ 交換比特置，並將 $i n d$ 右邊的數進行昇序排列。

代碼

    int findInd(int[] a) {
     // 從右往左找，找到一個下標，其右邊所有數字都是從大到小，如1.432，
        // 那麼，需要從432（即所有逆序排列的數中找到一個最小的，即2），替換1，並且讓143昇序排列
        int ind = a.length-1;
        while(ind > 0) {
    
            if(a[ind] <= a[ind-1]) ind--;
            else break;
        }
        return ind-1;
	}
	
	void next_permutation(int[] a) {
    
		int ind = findInd(a);
		if(ind == -1) {
    
			Arrays.sort(a);
		}
		else {
    
			int tar = -1;
			for(int i = a.length-1; i > ind; i--) {
    
				if(a[i] > a[ind]) {
    
					tar = i;
					break;
				}
			}
			int t = a[ind]; a[ind] = a[tar]; a[tar] = t;
			Arrays.sort(a, ind+1, a.length);
		}
	}