[Leetcode 1053]Previous Permutation With One Swap

原题说明

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

解题思路

我们找到A当中需要交换的位置left和right：
left的位置应当尽量往右：应当为A从右往左第一个变大的位置，因为其右边肯定有比其小的值了。
找到left的位置后，right应当是left右侧最大的数：
由于left右侧为从右往左递减的序列（从左往右递增），所以需要从右往左找到第一个大于A[left]的数A[right]。
如果A[right]有连续相同的数，比如[3, 1, 1, 3]中中间连续的1，那么我们希望right指向最左侧的那个1。
所以我们还需要继续将right向左移直到A[right] != A[right - 1]。
此时交换A[right]与A[left]，并返回A即可。

示例代码 (cpp)

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        if (A.size() <= 1) {
            return A;
        }
        // 找到从右往左第一个增大的位置left, 比如[3 1 1 3]中index 0
        int left = A.size() - 2;
        while (left >= 0 && A[left] <= A[left + 1]) {
            --left;
        }
        if (left < 0) {
            return A;
        }
        // 找到left右侧，从右往左第一个比A[left]小的位置right，比如[3 1 1 3]中index 2
        int right = A.size() - 1;
        while (A[right] >= A[left]) {
            --right;
        }
        // 从A[right]开始向左，最左边的连续与A[right]相同的位置，比如 [3 1 1 3]中index 1
        while (A[right] == A[right - 1]) {
            --right;
        }
        swap(A[left], A[right]);
        return A;
    }
};

示例代码 (java)

public class Solution {
    public int[] prevPermOpt1(int[] A) {
        // 1. 边界情况处理
        if (A.length == 1) {
            return A;
        }
 
        // 2. 找左边要交换的位置
        int left = A.length - 2;
        while (left >= 0) {
            if (A[left] > A[left + 1]) {
                break;
            }
            left--;
        }
 
        // 2.1 如果一直递减
        if (left < 0) {
            return A;
        }
 
        // 3. 找右边 第一个小于 left 的值
        int right = A.length - 1;
        while (A[right] >= A[left]) {
            right--;
        }
 
        // 4. 向左错位，如果 right 的左边 跟 right 一样
        int rightValue = A[right];
        while (A[right] == rightValue) {
            right--;
        }
        right++;
 
        // 5. 交换
        int temp = A[left];
        A[left] = A[right];
        A[right] = temp;
 
        return A;
    }
}

示例代码 (python)

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
 
        # 1. 边界情况处理
        if len(A) == 1 :
            return A
 
        # 2. 找左边要交换的位置
        left = len(A) - 2
        while left >= 0 :
            if A[left] > A[left + 1] :
                break
            left -= 1
        else :
            # 2.1 如果一直递减
            return A
 
        # 3. 找右边 第一个小于 left 的值
        right = len(A) - 1
        while A[right] >= A[left] :
            right -= 1
        
        # 4. 向左错位，如果 right 的左边 跟 right 一样
        right_value = A[right]
        while (A[right] == right_value) :
            right -= 1
        right += 1
 
        # 5. 交换
        A[left], A[right] = A[right], A[left]
 
        return A

复杂度分析

时间复杂度: O(N)
空间复杂度: O(1)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！