当前位置: 首页 > news >正文

【每日一题Day166】LC1053交换一次的先前排列 | 贪心

交换一次的先前排列【LC1053】

给你一个正整数数组 arr(可能存在重复的元素),请你返回可在 一次交换(交换两数字 arr[i]arr[j] 的位置)后得到的、按字典序排列小于 arr 的最大排列。

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

虽然写出来了,但是花了55分钟…
还是有思路但是思路不清晰,然后直接敲代码,改来改去,老毛病了
笔试绝对ggg
看了别人的贪心,感觉自己笨笨的

  • 思路:贪心

    假设交换的左边元素为 a r r [ i ] arr[i] arr[i],右边的元素为 a r r [ j ] arr[j] arr[j]

    • 怎样交换一次可以使字典序减小?

      交换元素 a r r [ i ] > a r r [ j ] arr[i]>arr[j] arr[i]>arr[j]时,可以使字典序较小,所以数组必须是非递增的

    • 如何使字典序小于原数组的情况下最大?【贪心】

      保留前面高位部分的数组,尽可能交换低位部分的数组,即尽可能最小化 j j j的同时,最大化 i i i

      枚举每个右端点,此时的右端点 r r r必须小于等于 n u m s [ j ] nums[j] nums[j],找到在 [ i , r − 1 ] [i,r-1] [i,r1]范围内,从右往左第一个大于其的左端点进行交换

      • 如果 a r r [ r ] > a r r [ j ] arr[r] > arr[j] arr[r]>arr[j], 那么从右往左第一个大于 a r r [ r ] arr[r] arr[r]的左端点一定在i的左边包括i,那么我们无法获得比目前的排列更大的排列
      • 如果 a r r [ r ] = = a r r [ j ] arr[r] == arr[j] arr[r]==arr[j], 那么从右往左第一个大于 a r r [ r ] arr[r] arr[r]的左端点还是为 i i i,只需要修改右端点
      • 如果 a r r [ r ] < a r r [ j ] arr[r] < arr[j] arr[r]<arr[j], 那么 l l l需要在 [ i + 1 , r − 1 ] [i+1,r-1] [i+1,r1]的范围内才可能是字典序增大
  • 实现

    class Solution {
        public int[] prevPermOpt1(int[] arr) {
            int n = arr.length;
            int l = 0;
            // 升序数组本身就是最小排列
            while (l < n - 1 && arr[l] <= arr[l + 1]){
                l++;
            }
            if (l == n - 1) return arr; // 升序数组
            // 非升序数组 枚举每个右端点 找到从右往左第一个大于其的左端点进行交换
            // 之后交换的右端点必须小于等于arr[j],并且左端点l必须大于i才能使交换结果变小
            // 如果arr[r] > arr[j], 那么从右往左第一个大于arr[r]的左端点一定在i的左边包括i,那么我们无法获得比目前的排列更大的排列
            // 如果arr[r] == arr[j], 那么从右往左第一个大于arr[r]的左端点还是为i,只需要修改右端点
            // 如果arr[r] < arr[j], 那么l需要在[i+1,r-1]的范围内才可能是字典序增大
            int i = -1, j = -1;// 记录最终的交换结果
            for (int r = n - 1; r > i; r--){
                if (j != -1 && arr[r] > arr[j]) continue;
                if (j != -1 && arr[r] == arr[j]) {
                    j = r;
                    continue;
                }
                for (l = r - 1; l >= (i != -1 ? i + 1 : 0); l--){
                    if (arr[l] > arr[r]){
                        i = l;
                        j = r;
                        break;
                    }
                }
            }
            // 交换
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            return arr;
        }
    }
    
    • 复杂度
      • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
      • 空间复杂度: O ( 1 ) O(1) O(1)
  • 别人的贪心
    我们先从右到左遍历数组,找到第一个满足 a r r [ i − 1 ] > a r r [ i ] arr[i−1]>arr[i] arr[i1]>arr[i]的下标 i i i,此时 a r r [ i − 1 ] arr[i−1] arr[i1]就是我们要交换的数字,我们再从右到左遍历数组,找到第一个满足 a r r [ j ] < a r r [ i − 1 ] arr[j]<arr[i−1] arr[j]<arr[i1] a r r [ j ] ≠ a r r [ j − 1 ] arr[j] \neq arr[j - 1] arr[j]=arr[j1] 的下标 j,此时我们交换 a r r [ i − 1 ] arr[i−1] arr[i1] a r r [ j ] arr[j] arr[j] 后返回即可。

class Solution {
    public int[] prevPermOpt1(int[] arr) {
        int n = arr.length;
        for (int i = n - 1; i > 0; --i) {
            if (arr[i - 1] > arr[i]) {
                for (int j = n - 1; j > i - 1; --j) {
                    if (arr[j] < arr[i - 1] && arr[j] != arr[j - 1]) {
                        int t = arr[i - 1];
                        arr[i - 1] = arr[j];
                        arr[j] = t;
                        return arr;
                    }
                }
            }
        }
        return arr;
    }
}

作者:ylb
链接:https://leetcode.cn/problems/previous-permutation-with-one-swap/solutions/2205403/python3javacgotypescript-yi-ti-yi-jie-ta-pxxt/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
  • 复杂度
    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( 1 ) O(1) O(1)

相关文章:

  • 蓝桥杯 --- 递归与递推(习题)
  • Ubuntu搭建web站点并发布公网访问【内网穿透】
  • 【我在异世界学Linux】认识操作系统 | 理解管理 | 系统调用(System Call)
  • 【Elastic (ELK) Stack 实战教程】07、Logstash 快速入门及 Input、Filter 插件讲解
  • 版本控制 | 告别繁琐,P4VJS带来全新的Diff体验
  • 老鼠迷宫,汉诺塔,八皇后,回溯算法案例
  • MATLAB :【12】手把手教你在Linux以命令行方式(静默方式/非图形化方式)安装MATLAB(正版)
  • 数据库MySQL/Navicat+商品购物系统+Java实现(超详细讲解)
  • 大文件分片上传的实现【前后台完整版】
  • Chatgpt 指令收集
  • 2022国赛14:2022国赛正式题域控制器的迁移
  • 【IAR工程】STM8S208RB基于ST标准库内部EEPROM使用
  • springcloud整合knike4j聚合微服务接口文档
  • 学会这些方法,扩展磁盘分区还不是轻轻松松?
  • Chat GPT和飞书机器人,真的有那么多联系嘛?
  • Pikachu登录爆破之token爆破解析
  • Spring Cloud Alibaba 应用如何平滑迁移至 IPv6?
  • 2816. 判断子序列(双指针)
  • 技术宅小伙:关于前端的那些你不知道的事
  • [Python] 常用运算符
  • 电加热油锅炉工作原理_电加热导油
  • 大型电蒸汽锅炉_工业电阻炉
  • 燃气蒸汽锅炉的分类_大连生物质蒸汽锅炉
  • 天津市维修锅炉_锅炉汽化处理方法
  • 蒸汽汽锅炉厂家_延安锅炉厂家
  • 山西热水锅炉厂家_酒店热水 锅炉
  • 蒸汽锅炉生产厂家_燃油蒸汽发生器
  • 燃煤锅炉烧热水_张家口 淘汰取缔燃煤锅炉
  • 生物质锅炉_炉
  • 锅炉天然气_天燃气热风炉