网站建设目的及意义,企业网站设计服务公司,网站目录爬行,网站栏目功能分析2024华为OD机试#xff08;E卷D卷C卷#xff09;最新题库【超值优惠】Java/Python/C合集 题目描述
给定参数n#xff0c;从1到n会有n个整数:1,2,3,.,n#xff0c;这n个数字共有 n!种排列。按大小顺序升序列出所有排列情况#xff0c;并-一标记#xff0c;当n3时,所有排列… 2024华为OD机试E卷D卷C卷最新题库【超值优惠】Java/Python/C合集 题目描述
给定参数n从1到n会有n个整数:1,2,3,.,n这n个数字共有 n!种排列。按大小顺序升序列出所有排列情况并-一标记当n3时,所有排列如下:
“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)!。比如 n3则有 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) {// 初始化可选数字列表ListInteger 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 algorithmusing namespace std;string getPermutation(int n, int k) {// 初始化可选数字列表vectorint 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. 排列序列困难 整理题解不易 如果有帮助到您请给点个赞 ❤️ 和收藏 ⭐让更多的人看到。
