面试题 16.16. 部分排序

2023-11-12

题目链接:https://leetcode-cn.com/problems/sub-sort-lcci/

思路如下:

在这里插入图片描述

从左往右看,正序应该是逐渐变大,最右逆序对所在的位置就是我们要求的右边界。

从右往左看,正序应该是逐渐变小,最左逆序对所在的位置就是我们要求的左边界。

求右边界和求左边界的过程是对称的。

从左往右扫描,记录扫描过的数中的最大值 max,如果发现当前值小于最大值,则记录它的位置 right,最终 right 保存的就是我们要求的右边界。

从右往左扫描,记录扫描过的数中的最小值 min,如果发现当前值大于最小值,则记录它的位置 left,最终 left 保存的就是我们要求的左边界。

Java代码如下:

class Solution {
    public int[] subSort(int[] array) {
        if (array.length == 0)  return new int[] {-1, -1};

        int max = array[0]; // 记录扫描过的数中的最大值
        int right = -1; // 记录最右逆序对所在的位置
        for (int i = 1; i < array.length; i++) {
            int t = array[i];
            if (t < max) {
                right = i;
            } else {
                max = t;
            }
        }

        if (right == -1)    return new int[] {-1, -1};

        int min = array[array.length - 1]; // 记录扫描过的数中的最小值
        int left = -1; // 记录最左逆序对所在的位置
        for (int i = array.length - 2; i >= 0; i--) {
            int t = array[i];
            if (t > min) {
                left = i;
            } else {
                min = t;
            }
        }

        return new int[] {left, right};
    }
}

C++代码如下:

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

面试题 16.16. 部分排序 的相关文章

  • 自学SQL习题答案整理(lesson4--)

    前几天看到一个学SQL的网站 感觉挺好的 但是比较少人用 链接 自学SQL 在这里放上一部分题目的答案 自己在mysql里实现了一下 方便以后再做这个练习的时候自查 主要是学习一些查询语句的运用 SELECT distinct direct
  • 力扣算法合集

    algo 鸡汤篇 排序算法 二叉树 哈希表 栈和队列 数组 链表 字符串 算法套路 双指针 排序 贪心思想 二分查找 搜索 动态规划 斐波那契数列 矩阵路径 数组区间 分割整数 最长递增子序列 01背包 股票交易 字符串编辑 算法题解 动态
  • 突破Cloudflare验证码的秘密方法

    Cloudflare是一种广泛使用的验证码方式 它旨在取代传统的CAPTCHA 提供更简单 更私密的验证方式 以区分真实用户和机器人 然而 对于爬虫工程师而言 这也带来了一些挑战 理解Cloudflare验证码的工作原理 在突破Cloudf
  • 手把手带你理解Vue的列表渲染?

    概念 v for 指令基于一个数组来渲染一个列表 v for 指令需要使用 item in items 形式的特殊语法 其中 items 是源数据数组 而 item 则是被迭代的数组元素的别名 2 代码

随机推荐

  • 关于PN节为什么会形成电场

    这个问题我纠结了很久 后面终于弄明白了 来备注一下 防止下次又忘记了 首先 我们了解一下P型半导体和N型半导体 P型半导体 硅晶体在参入 3价元素 用硼来举例 后 硅原子会和硼原子形成共价键 形成共价键的原因我们不需要知道 就当它们发生了反
  • unity 第二次作业

    3D游戏设计 Unity 一 简答题 1 GameObject 和 Assets的区别和联系 是游戏中实实在在的游戏项目文件夹中所需要堆放的资源 比如 var obj Resource Load Prefabs testItem 这个obj
  • 23哈尔滨工程大学计算机电子信息复试经验

    哈尔滨工程大学计算机电子信息复试经验 0 前言 1 笔试 2 机试 2 1 备考分析 2 2 备考建议 3 面试 3 1 政治 3 2 英语 3 3 专业基础 3 4 工程项目 0 前言 今年的复试拖的太长了 复试要求 名单等迟迟不出 复试
  • React Hooks 使用详解

    本文对 16 8 版本之后 React 发布的新特性 Hooks 进行了详细讲解 并对一些常用的 Hooks 进行代码演示 希望可以对需要的朋友提供点帮助 一 Hooks 简介 Hooks 是 React v16 7 0 alpha 中加入
  • 多益网络校招笔试题(前端工程师)

    1 写出inline和inline block的差别 布局方式相同 唯一的区别在inline block可以设置宽高 inline不可以 另外 inline设置上下内边距和上下外边距会造成一些mess 详见 What is the diff
  • 源码编译安装部署LAMP平台(使用Apache,MySQL与PHP搭建Discuz论坛实例)

    文章目录 一 LAMP平台与编译安装 一 LAMP平台概述 二 构建LAMP平台顺序 二 编译安装的优点 三 各组件的主要作用 二 部署步骤 一 编译安装Apache httpd服务 二 编译安装mysqld 服务 三 编译安装PHP 解析
  • 一定能用到的简单但实用的五种按钮样式(HTML+CSS步骤详解,含详细注释)

    前言一 按钮在前端开发中往往是一个必不可少的元素 也有许多精美好看的样式资源供开发者直接使用 但博主认为 对于初学者而言 总是去cv别人做好的 而不理解其中的原理 是很不好的 本人作为一名计科的学生 在大二也选修了校内的前端基础教程的课 但
  • 【Blender学习】界面

    界面 改变语言 学习笔记 改变语言 将blender改变成中文可以通过一下步骤 1 选择Files gt user preference 2 选中右下角inernational Fonts里的inerface和tooltips 再选择lan
  • Xmake实战---xmake 与 vscode 集成环境使用

    xmake vscode 插件介绍 我们之前的所有实验 都是使用 xmake 的命令行程序在终端下操作完成的 这对于一些初学者来说还是有不少门槛的 并且操作起来也不能够像其它 IDE 等带有可视化界面的开发环境那样顺手 尤其是代码的编辑 编
  • 05-RabbitMQ之原生API使用

    使用RabbitMQ提供的原生客户端API进行交互 一 Maven依赖
  • Tailwind CSS入门(二)——基本介绍和特性

    上一篇文章简要的介绍了原子类CSS 以及个人对语义化 原子化的一些经验和理解 从这篇文章开始 正式开始分享Tailwind CSS的特性 使用和技巧 Tailwind CSS是一个为快速开发而精心设计的原子类CSS框架 在此我们将搭建一个V
  • Vivado初体验LED工程

    文章目录 前言 一 PL 和 PS 二 LED 硬件介绍 三 创建 Vivado 工程 四 创建 Verilog HDL 文件 五 添加管脚约束 六 添加时序约束 七 生成 BIT 文件 八 仿真测试 九 下载测试 前言 本节我们要做的是熟
  • 压力测试-JMeter安装、入门、结果分析

    目录 1 写在前面 2 常用压测工具 3 压测机环境准备 JMeter部署 3 1 JMeter下载安装 启动 配置 3 2 入门案例 3 2 3 压测结果解释 3 2 4 线程属性参数原理 1 写在前面 等到服务上线后 在业务压力的冲击下
  • 我的毕业论文

    摘要 信息时代的到来 给电子商务带来了无限活力 电子商务网站已经显示出欣欣向荣的繁荣景象 基于这一历史背景 本论文介绍了基于J2EE标准规范 并采用其推荐的实现技术JSP java server pages Servlet等对一个典型电子商
  • STM32串口中断ORE问题记录

    首先感谢 今天也迟到 提供的思路 原文博客如下 https blog csdn net qq 34401994 article details 76359581 背景 STM32F030芯片 485串口使用MDA 中断方式收发数据 问题 串
  • Selenium Python 框架之 BasePage页面封装写法

    coding utf 8 Time 2019 10 25 Author carl dj from public common log import Logger from config import globalparam from sel
  • python和java哪个更值得学?

    在编程界经常会引发一个讨论 就是python和Java哪个更值得学 Java语言具有跨平台的特性 在应用范围上有许多选择的余地 而Python在这几年的火热程度丝毫没有减退 个人观点 看学习的目的 如果想在互联网公司找个稳定的工作那就学习J
  • Spring Boot的创建和使用

    目录 什么是Spring Boot Spring Boot的优点 Spring Boot项目的创建 通过idea创建Spring Boot项目 1 安装插件 2 new project 3 选择Spring Boot项目 选择合适的jdk版
  • 容易让单片机程序跑飞的原因

    1 意外中断 是否打开了某个中断 但是没有响应和清除中端标志 导致程序一直进入中断 造成死机假象 2 中断变量处理不妥 若定义某些会在中断中修改的全局变量 这时要注意两个问题 首先为了防止编译器优化中断变量 要在这些变量定义时前加volat
  • 面试题 16.16. 部分排序

    题目链接 https leetcode cn com problems sub sort lcci 思路如下 从左往右看 正序应该是逐渐变大 最右逆序对所在的位置就是我们要求的右边界 从右往左看 正序应该是逐渐变小 最左逆序对所在的位置就是