【Leetcode】1053. Previous Permutation With One Swap（138周赛第三题）（数组上一个排列的组合-只交换两个数）

女爷i 2022-01-27 11:13 113阅读 0赞

Given an array `A` of positive integers (not necessarily distinct), return the lexicographically largest permutation that is smaller than `A`, that can be **made with one swap** (A *swap* exchanges the positions of two numbers `A[i]` and `A[j]`). If it cannot be done, then return the same array.

**Example 1:**

Input: [3,2,1]
    Output: [3,1,2]
    Explanation: Swapping 2 and 1.

**Example 2:**

Input: [1,1,5]
    Output: [1,1,5]
    Explanation: This is already the smallest permutation.

**Example 3:**

Input: [1,9,4,6,7]
    Output: [1,7,4,6,9]
    Explanation: Swapping 9 and 7.

**Example 4:**

Input: [3,1,1,3]
    Output: [1,3,1,3]
    Explanation: Swapping 1 and 3.

**Note:**

1.  `1 <= A.length <= 10000`
2.  `1 <= A[i] <= 10000`

题目大意：

给出一个数组找出这个数组，在只交换一组数的情况下，求解出第一个比当前小的排列组合。

解题思路：

从后向前遍历整个数组，找出第一个有上升趋势的数，这个数字是目标位置，那么它需要与谁进行交换？

再次从后向前，第一个比当前数小的数。两者交换。

class Solution {
    public:
        vector<int> prevPermOpt1(vector<int>& A) {
            int idx = A.size();
            for(int i=A.size()-1;i>=1;i--){
                if(A[i]>=A[i-1]){
                    continue;
                }else{
                    idx = i-1;
                    break;
                }
            }
            if(idx == A.size()) return A;
            for(int i = A.size()-1; i>idx ;i--){
                if(A[i]<A[idx]){
                    int cc = A[i];
                    A[i] =A[idx];
                    A[idx] = cc;
                    break;
                }
            }
            return A;
        }
    };