Java编程实战6:排序序列

news/2024/3/28 20:24:19/文章来源:https://blog.csdn.net/m0_71905144/article/details/127538406

目录

  • 排序序列
    • 题目
      • 示例 1
      • 示例 2
      • 示例 3
      • 提示
    • 解答
      • 解题思路
      • 完整代码

排序序列

题目

给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:

  1. “123”
  2. “132”
  3. “213”
  4. “231”
  5. “312”
  6. “321”

给定 n 和 k,返回第 k 个排列。

示例 1

输入:n = 3, k = 3
输出:“213”

示例 2

输入:n = 4, k = 9
输出:“2314”

示例 3

输入:n = 3, k = 1
输出:“123”

提示

  • 1 <= n <= 9
  • 1 <= k <= n!

解答

解题思路

要想解决本题,首先需要了解一个简单的结论:
对于n个不同的元素(例如数1,2, … .,n ),它们可以组成的排列总数目为n!。对于给定的n和k,我们不妨从左往右确定第k个排列中的每一个位置.上的元素到底是什么。我们首先确定排列中的首个元素a1。根据上述的结论,我们可以知道:以1为a1的排列一共有(n- 1)!个;以2为a1的排列一共有(n- 1)!个;以n为a1的排列一共有(n- 1)!由于我们需要求出从小到大的第k: 个排列,因此:如果k:< (n- 1)! ,我们就可以确定排列的首个元素为1 ;如果(n- 1)!< k:≤2.(n- 1)!,我们就可以确定排列的首个元素为2 ;如果(n- 1).(n- 1)! < k≤n.(n一我们就可以确定排列的首个元素为n。因此,第k个排列的首个元素就是:k- 1a1 =(n- 1)!-+1其中x」表示将X向下取整。当我们确定了a1 后,如何使用相似的思路,确定下一个元素a2呢?实际上,我们考虑以a1为首个元素的所有排列:
以[1,n]\a1 最小的元素为a2的排列一共有(n- 2)!个;以[1,n]\a1 次小的元素为a2的排列一共有(n-2)!个;以[1,n]\a1最大的元素为 a2的排列一共有(n-2)!个;其中[1,n]\a1表示包含1,2,…n中除去a1以外元素的集合。这些排列从编号(a1- 1).(n-1)!开始,到a1.(n- 1)!结束,总计(n-1)!个,因此第k个排列实际.上就对应着这其中的第k:’=(k-1) mod(n- 1)!+1个排列。这样一来,我们就把原问题转化成了一个完全相同但规模减少1的子问题:求[1,n]\a1这n-1个元素组成的排列中,第k’小的排列。算法设第k; 个排列为A1,A2, … . ,An,我们从左往右地确定每一个元素ai。我们用数组valid记录每一个元素是否被使用过。我们从小到大枚举i :我们已经使用过了i- 1个元素,剩余n- i+ 1个元素未使用过,每一个元素作为a;都对应着(n- i)! 个排列,总计(n-i+ 1)! 个排列; .因此在第k个排列中,a;即为剩余未使用过的元素中第k- 1+1小的元(n- i)!素;在确定了a;后,这n-i+1个元素的第k个排列,就等于a;之后跟着剩余n-i个元素的第(k:- 1) mod(n-i)!+1个排列。在实际的代码中,我们可以首先将k; 的值减少1,这样可以减少运算,降低代码出错的概率。对应上述的后两步,即为:因此在第k: 个排列中,A;即为剩余未使用k过的元素中第((n-i)!-+1小的元素;在确定了a;后,这n-i+1个元素的第. k个排列,就等于a;之后跟着剩余n-i个元素的第k mod(n- i)!个排列。实际上,这相当于我们将所有的排列从0开始进行编号。

完整代码

class Solution {public String getPermutation(int n, int k) {int[] factorial = new int[n];        factorial[0] = 1;        for (int i = 1; i < n; ++i) {            factorial[i] = factorial[i - 1] * i;        }        --k;        StringBuffer ans = new StringBuffer();        int[] valid = new int[n + 1];        Arrays.fill(valid, 1);        for (int i = 1; i <= n; ++i) {            int order = k / factorial[n - i] + 1;            for (int j = 1; j <= n; ++j) {                order -= valid[j];                if (order == 0) {                    ans.append(j);                    valid[j] = 0;                    break;                }            }            k %= factorial[n - i];        }        return ans.toString();    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_218726.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【LeetCode每日一题】【单调队列】2022-10-26 862. 和至少为K的最短子数组 Java实现

文章目录题目链接题目思路前缀和暴力法优化一优化二另一种写法题目链接 https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/ 题目 思路 https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/solution/liang-zhang-tu-miao-dong-dan-dia…

【电子通识】芯片资料(数据手册/规格书)查询常用网站和方法

目录 1.AlldataSheet 网站&#xff08;建议使用&#xff09; 2.ICpdf 网站 3.CIC中国IC网 网站 4.datasheet&#xff08;不建议使用&#xff09; 5.半导小芯 &#xff08;建议使用&#xff09; 6.立创商城 &#xff08;建议使用&#xff09; 在做硬件的芯片选型、产品维修…

MySQL体系结构

MySQL体系结构初识MySQLOLTPOLAPSQL数据库术语MySQL体系结构连接池缓冲组件执行select语句的过程总结后言初识MySQL 按照数据结构来组织、存储和管理数据的仓库&#xff1b;是一个长期存储在计算机内的、有组织的、可共享的、统一管理的大量数据的集合。 MySQL是关系型数据库&…

从位运算理解位图

位图是一种较难理解的数据结构&#xff0c;想了解位图&#xff0c;我需要先温习一下基础&#xff0c;复习下一些二进制的知识 位运算 1个字节8个二进制位 二进制每逢二进一&#xff0c;下面是二进制对应的十进制转换方式 二进制十进制0000 00012^010000 00102^120000 00112…

Shell编程案例

Shell编程案例 文章目录Shell编程案例熟悉shell编程的有关机制&#xff0c;如标准流。学习Linux环境变量设置文件及其内容/etc/profile/etc/bashrc/etc/environment~/.profile~/.bashrc熟悉编程有关基础命令技巧和规则sed掌握shell 程序执行的三种基本方式使用for循环语句,完成…

万字长文的CSS与JavaScript简易学习

近期学习web笔记&#xff0c;可供参考 目录 css: css导入方式&#xff1a; css选择器&#xff1a; javascript: javascript介绍&#xff1a; js引入方式&#xff1a; js书写语法&#xff1a; js变量&#xff1a; 5种原始类型&#xff1a; 运算符&#xff1a; JavaScr…

Spring Aop的学习(一):Spring Aop的简单入门

1. 什么是AOP AOP(Aspect Oriented Programming):面向切面编程,是OOP(面向对象编程)的一个延续,其和OOP一样,也是一种编程思想。不过AOP是一种横向开发模式。 2. AOP的作用及应用场景作用 AOP的主要作用就是减少代码量,提高代码的可重用性,有利于未来的可操作性与可维护性…

2022-2023-1 20221424《计算机基础与程序设计》第9周学习总结

2022-2023-1 20221424《计算机基础与程序设计》第9周学习总结 作业信息这个作业属于哪个课程 2022-2023-1-计算机基础与程序设计这个作业要求在哪里 2022-2023-1计算机基础与程序设计第一周作业这个作业的目标 操作系统责任,内存与进程管理,分时系统,CPU调度,文件、文件系统…

《JavaSE-第十五章》之文件(二)

前言 在你立足处深挖下去,就会有泉水涌出!别管蒙昧者们叫嚷:“下边永远是地狱!” 博客主页&#xff1a;KC老衲爱尼姑的博客主页 博主的github&#xff0c;平常所写代码皆在于此 刷题求职神器 共勉&#xff1a;talk is cheap, show me the code 作者是爪哇岛的新手&#xff0c;水…

neovim图标显示乱码,utf8字体显示乱码(Windows10和Centos安装nerd-fonts)

前言 作为一名想成为大神的菜鸟程序员&#xff0c;一个牛X的代码编辑环境是必不可少的&#xff0c;在这里我推荐neovim和emacs。我使用的是neovim&#xff0c;github上有neovim-from-scratch工程可以一步一步学习搭建&#xff0c;B站上也有相关视频可供学习&#xff0c;在这里…

升级python环境时gdal出现缺少proj的问题

gdal在做坐标转换时报出如此的错误。原系统的代码没有改变&#xff0c;为了更新sentinelhub包&#xff0c;将python环境由3.6升级至3.7。升级了python环境之后&#xff0c;所有相关的py包和第三方库重新进行安装。安装过程中基本没有遇到问题。但是在运行代码时gdal报出错误。 …

IDEA全局搜索快捷键方法

1、CtrlN 按名字搜索类 相当于eclipse的ctrlshiftR&#xff0c;输入类名可以定位到这个类文件&#xff0c;就像IDEA在其他的搜索部分表现一样&#xff0c;搜索类名也能对你所要搜索的内容多个部分进行匹配&#xff0c;而且如果能匹配的自己写的类&#xff0c;优先匹配自己写的类…

java实验报告4;

一、实验目的:【目的要求】 了解接口和抽象类的使用 熟悉类中成员的定义及权限的设定 掌握完整类的设计 【注意事项】 注意电源插座的用电安全&#xff1b; 遵守计算机的使用注意事项&#xff1b; 防范病毒。 二、使用工具 电脑 window系统 JDK环境 eclipse开发环境…

本博主二哈喇子!特此声明

免责声明 本博主二哈喇子&#xff01;为了避免各种纠纷&#xff0c;特做如下说明: 本博主一向尊重他人的知识产权&#xff0c;同时也注意保护自己的知识产权&#xff0c;因此建议您在进入本博客的各个页面前&#xff0c;请务必仔细阅读本声明。 一切网民以任何方式在进入本博客…

模拟登陆系统

1.问题 日常生活中我们会遇到许多需要密码来登陆账户的场景&#xff0c;如何使用Java来创建此类登陆代码呢&#xff1f; 2.方法 import java.util.Scanner; public static void main (String[] args) { Scanner sc new Scanner (System.in); int count 3; while(cou…

控制“恶意”代码,安全运行沙箱类技术崛起

据CNNIC的最新估算&#xff0c;截至10月31日&#xff0c;我国上网用户人数达到5800万&#xff0c;上网计算机数升至2300万&#xff0c;从七月份至今&#xff0c;在短短的四个月间分别增加了1220万和687万。 这预示着我国互联网在经过一段时间的发展低潮之后正在开始回暖。 但…

贪婪算法(Huffman编码)

如果一个算法分阶段的工作&#xff0c;并且在每一个阶段都认为所做的决定是最好的&#xff0c;而不考虑将来的后果&#xff0c;这样的算法就叫做贪婪算法。贪婪算法只考虑当前局部的最优解&#xff0c;而不去考虑全局的情况&#xff0c;如果最终得到的结果是全局最优的&#xf…

【pytest官方文档】解读- 开发可pip安装的第三方插件

在上一篇的 hooks 函数分享中,开发了一个本地插件示例,其实已经算是在编写插件了。今天继续跟着官方文档学习更多知识点。 一个插件包含一个或多个钩子函数,pytest 正是通过调用各种钩子组成的插件,实现了配置、搜集、运行和报告的所有方面的功能。 通常 pytes t中的插件有…

OS实战笔记(7)-- Linux同步机制

上一篇笔记中对x86平台上原子变量、关中断、自旋锁和信号量的原理做了复习&#xff0c;本笔记回顾一下Linux使用的几种常用的同步机制。 Linux上的原子变量 Linux上提供了一个atomic_t类型表示原子变量。32位和64位版本的结构体定义如下&#xff1a; typedef struct {int coun…

文件描述符0,1,2+lseek()+共享文件覆盖解决

1.文件描述符0&#xff0c;1&#xff0c;2 程序开始运行时&#xff0c;有三个文件被自动打开&#xff0c;打开时分别使用了这三个文件描述符依次打开的三个文件分别是 /dev/stdin&#xff0c;/dev/stdout&#xff0c;/dev/stderr /dev/stdin 标准输入文件 程序开始运行时&…