第k个排列 - 华为OD统一考试(E卷)
2024华为OD机试(E卷+D卷+C卷)最新题库【超值优惠】Java/Python/C++合集

题目描述
给定参数n,从1到n会有n个整数:1,2,3,.,n,这n个数字共有 n!种排列。按大小顺序升序列出所有排列情况,并-一标记,当n=3时,所有排列如下:
“123”
“132”
“213”
“231”
“312”
“321”
给定n 和 k,返回第k个排列。
输入描述
输入两行,第一行为n,第二行为k,给定n的范国是[1,9],给定k的范围是[1,n!]。
输出描述
输出排在第k位置的数字。
示例1
输入:
3
3输出:
213说明:
3的排列有123 132 213...,那么第3位置的为213
示例2
输入:
2
2输出:
21说明:
2的排列有12 21,那么第2位置的为21
题解
这道题属于排列组合问题,需要找到第
k个排列。给定数字n,有n!种排列。通过 数学方法 来求解,我们可以避免生成所有排列,直接通过数学推理一步步缩小范围,找到目标排列。思路
- 数学推导:
- 每个位置的元素可以通过判断当前是第几组排列来决定。对于排列的第一位,有
n种选择,而剩下的n-1位对应的排列数为(n-1)!。- 比如
n=3,则有3!=6种排列,其中每两组排列会以1开头、2开头、或者3开头。所以第一个位置的数字可以通过k来确定,依次缩小范围直到找出第k个排列。- 逐步计算:
- 计算
(n-1)!,确定第一个数字的范围;- 更新
k的值,并继续计算下一个位置的数字,直到生成完整排列。- 关键技巧:
- 用一个数字列表存储所有可以选择的数字;
- 根据
k来选择当前的数字,并将其从候选列表中移除;- 每次计算第
i位时,将k减去已经完成的所有组数。时间复杂度
- 由于每次计算需要根据
(n-1)!来确定当前数字,时间复杂度为O(n)。
Java
import java.util.*;
/*** @author code5bug*/
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();System.out.println(getPermutation(n, k));}public static String getPermutation(int n, int k) {// 初始化可选数字列表List<Integer> nums = new ArrayList<>();for (int i = 1; i <= n; i++) {nums.add(i);}StringBuilder result = new StringBuilder();k--; // 转换为从 0 开始计数// 逐位确定排列int fact = 1;for (int i = 1; i < n; i++) {fact *= i; // 计算 (n-1)!}for (int i = n; i > 0; i--) {// 确定当前位的索引int index = k / fact;result.append(nums.remove(index));// 更新 k 的值k %= fact;if (i > 1) {fact /= (i - 1); // 计算新的 (i-2)!}}return result.toString();}
}
Python
import mathdef get_permutation(n, k):# 初始化可选数字列表nums = [str(i) for i in range(1, n + 1)]# 结果数组result = []# 将 k 转为从 0 开始计数k -= 1# 逐位确定排列for i in range(n, 0, -1):# 计算 (i-1)! 的值fact = math.factorial(i - 1)# 选择当前位的数字index = k // factresult.append(nums.pop(index))# 更新 k 的值k %= fact# 返回结果字符串return ''.join(result)# 输入处理
if __name__ == "__main__":n = int(input())k = int(input())# 输出第 k 个排列print(get_permutation(n, k))
C++
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;string getPermutation(int n, int k) {// 初始化可选数字列表vector<int> nums;for (int i = 1; i <= n; i++) {nums.push_back(i);}string result;k--; // 转换为从 0 开始计数// 逐位确定排列int fact = 1;for (int i = 1; i < n; i++) {fact *= i; // 计算 (n-1)!}for (int i = n; i > 0; i--) {// 确定当前位的索引int index = k / fact;result += to_string(nums[index]);nums.erase(nums.begin() + index); // 从列表中移除该数字// 更新 k 的值k %= fact;if (i > 1) {fact /= (i - 1); // 计算新的 (i-2)!}}return result;
}int main() {int n, k;cin >> n >> k;cout << getPermutation(n, k) << endl;return 0;
}
相关练习题
| 题号 | 题目 | 难易 |
|---|---|---|
| 60. 排列序列 | 60. 排列序列 | 困难 |
整理题解不易, 如果有帮助到您,请给点个赞 ❤️ 和收藏 ⭐,让更多的人看到。🙏🙏🙏
相关文章:
第k个排列 - 华为OD统一考试(E卷)
2024华为OD机试(E卷D卷C卷)最新题库【超值优惠】Java/Python/C合集 题目描述 给定参数n,从1到n会有n个整数:1,2,3,.,n,这n个数字共有 n!种排列。按大小顺序升序列出所有排列情况,并-一标记,当n3时,所有排列…...
清理C盘缓存,电脑缓存清理怎么一键删除,操作简单的教程
清理C盘缓存是维护电脑性能、释放磁盘空间的重要步骤。以下是一个详细且操作简单的教程,旨在帮助用户通过一键或几步操作完成C盘缓存的清理。 1.使用Windows系统自带工具 磁盘清理 1.打开磁盘清理工具: -按下“WinE”打开文件资源管理器…...
网络安全-ssrf
目录 一、环境 二、漏洞讲解 三、靶场讲解 四、可利用协议 4.1 dict协议 4.2 file协议 4.3 gopher协议 五、看一道ctf题吧(长亭的比赛) 5.1环境 5.2开始测试 编辑 一、环境 pikachu,这里我直接docker拉取的,我只写原…...
c++刷题
17.电话号码的组合 来源于题解思路: 继承 CC14 KiKi设计类继承 #include <iostream> #include <memory> using namespace std; class Shape{ private:int x;int y; };class Rectangle:public Shape { public:Rectangle(int length,int width):Shape…...
艾丽卡的区块链英语小课堂
系列文章目录 复习昨日 文章目录 系列文章目录前言1.opaque2.deduplicates3.references4,intermix5.serializing6.streamline7.robust8.flexibility9.exotic10.nevertheless11. realize12.flavor13.subtract14.attach15.award 前言 欢迎来到艾丽卡的区块链英语小课堂&#x…...
计算机毕业设计 公寓出租系统的设计与实现 Java实战项目 附源码+文档+视频讲解
博主介绍:✌从事软件开发10年之余,专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ 🍅文末获取源码联系🍅 👇🏻 精…...
eclipse使用 笔记02
创建一个项目: 【File-->New-->Dynamic Web Project】 进入页面: Project name为项目命名 Target runtime:选择自己所对应的版本 finish创建成功: 创建成功后的删除操作: 创建前端界面: 【注意&a…...
基于C++实现(MFC)职工工作量统计系统
题目:职工工作量统计系统设计 1、问题描述 职工包括姓名、职工号、性别、年龄、所在部门、联系方式等信息。 工作量包括职工号、完成的产品数量等信息。 该设计系统能够对职工的工作量进行统计,并排出名次。注意,一个职工的工作量是可以多次…...
大家好,我叫Redis~
大家好,我是Redis!下面请通过我的故事来认识我吧。 1. 初次登场:为什么需要我 在“双十一”期间,商店被顾客挤得水泄不通,所有人都急着问:“这款商品还有库存吗?” 可怜的服务员(My…...
【鸿蒙】HarmonyOS NEXT星河入门到实战6-组件化开发-样式结构重用常见组件
目录 1、Swiper轮播组件 1.1 Swiper基本用法 1.2 Swiper的常见属性 1.3 Swiper的样式自定义 1.3.1 基本语法 1.3.2 案例小米有品 2、样式&结构重用 2.1 Extend:扩展组件(样式、事件) 2.2 Styles:抽取通用属性、事件 2.3 Builder:自定义构建函数(结构、样式、事…...
网络安全学习(五)Burpsuite
经过测试,发现BP需要指定的JAVA才能安装。 需要的软件已经放在我的阿里云盘。 (一)需要下载Java SE 17.0.12(LTS) Java Downloads | Oracle 1.2023版Burp Suite 完美的运行脚本的环境是Java17 2.Java8不支持 看一下是否安装成功,…...
多版本node管理工具nvm
什么是nvm? 在项目开发过程中,使用到vue框架技术,需要安装node下载项目依赖,但经常会遇到node版本不匹配而导致无法正常下载,重新安装node却又很麻烦。为解决以上问题,nvm:一款node的版本管理工…...
如何扫描试卷去除笔迹?4种方法还原整洁试卷
如何扫描试卷去除笔迹?扫描试卷去除笔迹,作为现代学习管理与评估的革新手段,不仅显著提升了试卷的整洁美观度,更在环保和资源再利用层面发挥了积极作用。它使得试卷的保存、分享与复习变得更加便捷高效,减少了纸质资源…...
介绍⼀下泛型擦除
1.是什么 泛型擦除(Type Erasure)是Java泛型实现中的一个重要概念。Java的泛型是通过类型擦除来实现的,这意味着在运行时,泛型信息(即类型参数的具体类型)是不可用的。编译器在编译时会对泛型代码进行擦除处…...
从底层原理上理解ClickHouse 中的 Distributed 引擎
ClickHouse 的 Distributed 引擎 是实现大规模分布式查询和高可用性的关键技术之一,它允许集群中的多个节点协同工作,提供横向扩展能力和负载均衡机制。在底层,Distributed 引擎通过一系列的机制和策略,确保数据的分布、查询的并行…...
社区志愿者服务系统小程序的设计
管理员账户功能包括:系统首页,个人中心,志愿者管理,社区管理,活动类型管理,志愿者活动管理,活动报名管理,活动签到管理,证书信息管理,系统管理 微信端账号功…...
echarts map地图动态下钻,自定义标注,自定义tooltip弹窗【完整demo版本】
在数据可视化中,地图是很重要的一个环节,很多时候需要展现的不仅是国家地图,还需要能从国家进入到省市。这个逐级进入的过程就是我们今天说的地图下钻。 地图下钻看起来很屌、很高大上,但是仔细琢磨一下,技术实现上真的…...
Python热频随机森林分类器算法模型模拟
🎯要点 研究发射测量斜率和时滞热频率表征,使用外推法计算三维磁场并定性比较使用基于焓的热演化环模型模拟每条线的热力学响应,测试低频、中频和高频热场景使用光学薄、高温、低密度等离子体的单位体积辐射功率或发射率公式等建模计算使用直…...
C++11新增特性:lambda表达式、function包装器、bind绑定
一、lambda表达式 1)、为啥需要引入lambda? 在c98中,我们使用sort对一段自定义类型进行排序的时候,每次都需要传一个仿函数,即手写一个完整的类。甚至有时需要同时实现排升序和降序,就需要各自手写一个类&…...
动态主题模型DTM(Dynamic topic model)简介及python代码
文章目录 DTM模型简介DTM实现1:gensim.models.ldaseqmodel包DTM实现2:gensim.models.wrappers.dtmmodel.DtmModel包DTM模型简介 DTM模型(Dynamic Topic Model)是一种用于文本数据分析的概率模型,主要用于发现文本数据背后的主题结构和主题的演化过程。DTM模型是LDA模型的…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...
ui框架-文件列表展示
ui框架-文件列表展示 介绍 UI框架的文件列表展示组件,可以展示文件夹,支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项,适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...
