LeetCode 1053. Previous Permutation With One Swap

2021年09月15日 阅读数:4
这篇文章主要向大家介绍LeetCode 1053. Previous Permutation With One Swap,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

原题连接在这里:https://leetcode.com/problems/previous-permutation-with-one-swap/html

题目:app

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.post

Example 1:ui

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

Example 2:url

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

Example 3:spa

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

Example 4:code

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

Note:htm

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

题解:blog

From right to left, find the first element A[i - 1] > A[i]. Mark first position = i - 1.element

If we can't find it, then there is no previouis perrmutation.

Then mark second position = i, and for j > i, find the last position that A[j] > A[j - 1] && A[j] < A[first]. If we find any, keep updating second position.

Swap first and second positions.

Time Complexity: O(n). n = A.length.

Space: O(1).

AC Java:

 1 class Solution {
 2     public int[] prevPermOpt1(int[] A) {
 3         if(A == null || A.length == 0){
 4             return A;
 5         }
 6         
 7         int n = A.length;
 8         int i = n - 1;
 9         while(i >= 1 && A[i] >= A[i - 1]){
10             i--;
11         }
12         
13         if(i == 0){
14             return A;
15         }
16         
17         int first = i - 1;
18         int second = i;
19         for(int j = i + 1; j < n; j++){
20             if(A[j] > A[j - 1] && A[j] < A[first]){
21                 second = j;
22             }
23         }
24             
25         int temp = A[first];
26         A[first] = A[second];
27         A[second] = temp;
28         return A;
29     }
30 }

相似Next Permutation.