1053. 交换一次的先前排列

╰+哭是因爲堅強的太久メ 2023-10-05 00:56 25阅读 0赞

给你一个正整数的数组 `A`（其中的元素不一定完全不同），请你返回可在 **一次交换**（交换两数字 `A[i]` 和 `A[j]` 的位置）后得到的、按字典序排列小于 `A` 的最大可能排列。

如果无法这么操作，就请返回原数组。

**示例 1：**

输入：arr = [3,2,1]
    输出：[3,1,2]
    解释：交换 2 和 1

**示例 2：**

输入：arr = [1,1,5]
    输出：[1,1,5]
    解释：已经是最小排列

**示例 3：**

输入：arr = [1,9,4,6,7]
    输出：[1,7,4,6,9]
    解释：交换 9 和 7

**示例 4：**

输入：arr = [3,1,1,3]
    输出：[1,3,1,3]
    解释：交换 1 和 3

**提示：**

*  `1 <= arr.length <= 104`
 *  `1 <= arr[i] <= 104`

import java.util.Arrays;
    
    public class Solution1053 {
    	public int[] prevPermOpt1(int[] A) {
    		int len = A.length;
    		int index = -1;
    		for (int i = len - 1; i > 0; i--) {
    			if (A[i - 1] > A[i]) {
    				index = i - 1;
    				break;
    			}
    		}
    		if (index == -1) {
    			return A;
    		}
    		int in = A[index];
    		int ans = A[index + 1];
    		int result = index + 1;
    		for (int j = index + 1; j < A.length; j++) {
    			if (A[j] < in && A[j] > ans) {
    				ans = A[j];
    				result = j;
    			}
    		}
    		A[index] = ans;
    		A[result] = in;
    		return A;
    	}
    
    	public static void main(String[] args) {
    
    		Solution1053 sol = new Solution1053();
    
    		int[] arr = { 3, 2, 1 };
    
    		System.out.println(Arrays.toString(sol.prevPermOpt1(arr)));
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，25人围观）

还没有评论，来说两句吧...

相关阅读

相关一篇文章读懂电路交换、报文交换和分组交换

1.详解电路交换（1）原理 (1)通信之前先要建立连接，通信完毕后要释放连接。也就是说通信一定要有三个阶段建立连接、通信、释放连接。 (2)在整个通信过程中，通

刺骨的言语ヽ痛彻心扉/ 2023年10月16日 15:42/ 0 赞/ 188 阅读

相关 1053. 交换一次的先前排列

给你一个正整数的数组 `A`（其中的元素不一定完全不同），请你返回可在一次交换（交换两数字 `A[i]` 和 `A[j]` 的位置）后得到的、按字典序排列小于 `A` 的最大

╰+哭是因爲堅強的太久メ/ 2023年10月05日 00:56/ 0 赞/ 26 阅读

相关【1790. 仅执行一次字符串交换能否使两个字符串相等】

package com.lfsun.main.demoleetcode.easy; import org.junit.Test; /

一时失言乱红尘/ 2023年10月03日 22:55/ 0 赞/ 18 阅读

相关 1053 正弦函数

题目描述输入x，计算上面公式的前10项和。输入输入一个实数x。输出输出一个实数，即数列的前10项和，结果保留3位小数。样例输入 Copy 1

桃扇骨/ 2023年05月31日 12:06/ 0 赞/ 83 阅读

相关测试 VS1053 的步骤

测试 VS1053 的步骤： 1. ram 测试，读到的值是0x83FF,则表明mcu 与 VS1053 之间 spi 通信成功，VS1053 工作正常。 2. si

- 日理万妓/ 2022年12月27日 08:48/ 0 赞/ 182 阅读

相关 Leetcode 1053. 交换一次的先前排列（DAY 128) ---- 贪心算法学习期（+1补）

原题题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nL

逃离我推掉我的手/ 2022年10月17日 04:08/ 0 赞/ 141 阅读

相关 Problem C: P1053

Problem C: P1053 Time Limit: 0 Sec Memory Limit: 128 MB Submit: 13 Solved: 1

心已赠人/ 2022年08月03日 11:55/ 0 赞/ 199 阅读

相关 HDU 1053 Entropy(贪心)

这道题是哈弗曼树+贪心； [哈夫曼树][Link 1]： [哈夫曼树][Link 1]又称最优[二叉树][Link 2]，是一种带权路径长度最短的二叉树。所谓树的带权路径长

痛定思痛。/ 2022年06月03日 00:12/ 0 赞/ 222 阅读

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

Given an array `A` of positive integers (not necessarily distinct), return the lexicogra

女爷i/ 2022年01月27日 11:13/ 0 赞/ 197 阅读

相关 HDU 1053 Entropy

Entropy Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe...

灰太狼/ 2021年03月28日 14:18/ 0 赞/ 476 阅读