给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第K个位置上的数字。

时间: 2023-05-31 16:02:33 浏览: 140
算法思路: 1.先求出给定正整数的位数n。 2.倒数第K个位置上的数字即为正数第n-K+1个位置上的数字。 3.将给定正整数从左往右数的每一位数字存入一个数组中。 4.输出数组中第n-K+1个位置上的数字即可。 算法实现: C++代码如下: ```cpp #include<iostream> #include<vector> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> nums(n); for(int i = 0; i < n; i++) cin >> nums[i]; cout << nums[n-k] << endl; return 0; } ``` Python代码如下: ```python n, k = map(int, input().split()) nums = list(map(int, input().split())) print(nums[n-k]) ```
相关问题

给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第k个位置上的数字

假设给定的正整数序列为a1, a2, ..., an,倒数第k个位置指的是从序列末尾往前数第k个位置,也就是第n-k+1个位置。 一种简单的做法是先遍历一遍序列,确定序列的长度n,然后再遍历一遍序列找到第n-k+1个位置的数。这种做法的时间复杂度为O(n),并不是最优的。 更高效的做法是使用双指针。首先让一个指针p1从序列开头向前移动k-1个位置,然后再让另一个指针p2从序列开头开始和p1一起向前移动,直到p1到达序列末尾为止。此时p2所指的位置就是倒数第k个位置。这种做法的时间复杂度为O(n),但是实际上只需要遍历一次序列,所以速度会比上一种做法快很多。

C语言 给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第K个位置上的数字。

算法思路: 1.定义一个计数器count,用来记录已经遍历的正整数的个数。 2.从第一个正整数开始遍历,每遍历一个正整数,count自增1。 3.当count等于K时,记录当前遍历到的正整数的值。 4.继续遍历,直到遍历完所有正整数。 5.返回记录的正整数的值。 算法实现: ```c #include <stdio.h> int findKthDigit(int* nums, int numsSize, int k) { int count = 0; int i; for (i = 0; i < numsSize; i++) { int num = nums[i]; while (num > 0) { count++; if (count == k) { return num % 10; } num /= 10; } } return -1; } int main() { int nums[] = {123, 456, 789}; int numsSize = 3; int k = 7; int digit = findKthDigit(nums, numsSize, k); printf("%d\n", digit); return 0; } ``` 算法分析: 时间复杂度:O(nm),其中n是正整数的个数,m是正整数的位数。因为要遍历所有的正整数,对于每个正整数,需要遍历它的每一位,所以时间复杂度是O(nm)。 空间复杂度:O(1),算法只使用了常数个额外的变量。

相关推荐

最新推荐

recommend-type

Python实现查找数组中任意第k大的数字算法示例

在Python编程中,查找数组中第k大的数字是一项常见的任务,尤其在数据分析和算法竞赛中。这个任务通常涉及到数组操作,排序以及高效的查找技术。在给定的示例中,介绍了一个利用分治思想实现的算法,类似于快速排序...
recommend-type

python分割一个文本为多个文本的方法

总的来说,Python提供了一种灵活且高效的方式来分割文本文件,通过查找特定的分隔符或模式,我们可以将一个大文件拆分为多个小文件,便于进一步的分析和处理。理解并掌握这些基本的文件操作技巧对于Python开发者来说...
recommend-type

判断一个无向图是否为连通图的方法

判断一个无向图是否为连通图是一个常见的问题,尤其在图论和算法设计中。解决这个问题的方法通常基于深度优先搜索(DFS)或广度优先搜索(BFS)。这两种方法都是遍历图中的所有节点,检查是否存在从任意一个节点出发可以...
recommend-type

Java实现计算一个月有多少天和多少周

这意味着如果一个月的第一天是周日,那么即使只有第一天,也会被视为完整的一周。同样,如果一个月的最后一天是周六,那么即使只有这一天,也会被算作最后一周的一部分。 在上述代码中,我们设置的日期为2010年的6...
recommend-type

python简单算法04:判断一个字符串是否为回文串的排列之一

给定一个问题,我们需要编写一个名为`palindromic`的函数,它接受一个字符串`s`作为参数,并返回一个布尔值,表示`s`是否可以被排列成一个回文串。 首先,我们需要理解解题的关键在于字符计数。一个字符串能够构成...
recommend-type

图书大厦会员卡管理系统:功能设计与实现

本资源是一份C语言实训题目,目标是设计一个图书大厦的会员卡管理程序,旨在实现会员卡的全流程管理。以下是详细的知识点: 1. **会员卡管理**: - 该程序的核心功能围绕会员卡进行,包括新会员的注册(录入姓名、身份证号、联系方式并分配卡号),以及会员信息的维护(修改、续费、消费结算、退卡、挂失)。 - **功能细节**: - **新会员登记**:收集并存储个人基本信息,如姓名、身份证号和联系方式。 - **信息修改**:允许管理员更新会员的个人信息。 - **会员续费**:通过卡号查询信息并计算折扣,成功续费后更新数据。 - **消费结算**:根据卡号查询消费记录,满1000元自动升级为VIP,并提供9折优惠。 - **退卡和挂失**:退卡时退还余额,删除会员信息;挂失则转移余额至新卡,原卡显示挂失状态。 - **统计功能**:按缴费总额和消费总额排序,显示所有会员的详细信息。 2. **软件开发过程**: - 遵循软件工程标准,需按照分析、设计、编码、调试和测试的步骤来开发程序。 - **菜单设计**:程序以菜单形式呈现,用户通过菜单选择操作项目,如选择录入、查询、挂失等。 3. **输入输出要求**: - 用户通过键盘输入数据,程序会提供清晰的提示信息,包括数据内容、格式和结束方式。 - 菜单界面清晰,包含各项功能选项,如“添加会员”、“查询信息”、“挂失处理”等。 4. **数据结构与函数设计**: - 使用`struct huiyuan`定义会员信息结构体,包含卡号、姓名、身份证号和电话号码字段。 - 设计`menu()`函数负责显示菜单,通过函数调用来执行不同操作的功能函数。 5. **优惠策略**: - 购书打折规则:满1000元享受95折,满2000元享受9折,满5000元享受8折。 通过这个C语言项目,学生将学习到如何运用结构体、函数、文件I/O以及用户交互等核心概念,实现一个实用的会员卡管理系统。同时,也将提升他们的编程逻辑思维、问题解决能力和项目管理能力。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

Spring Boot框架测试实践:单元测试、集成测试、端到端测试(确保代码质量与稳定性)

![Spring Boot框架测试实践:单元测试、集成测试、端到端测试(确保代码质量与稳定性)](https://img-blog.csdnimg.cn/direct/70e2d215a77445048e72c56ddce5fa95.png) # 1. Spring Boot测试概述 Spring Boot测试是用于测试Spring Boot应用程序的全面测试框架。它提供了一套丰富的功能,使开发人员能够编写各种类型的测试,从单元测试到端到端测试。Spring Boot测试框架基于JUnit和Mockito等流行的测试库,并与Spring Boot应用程序的特性和功能进行了无缝集成。 通过使
recommend-type

转换json的方法是json.tojsonString

"toJsonString"并不是JSON本身的标准方法,它通常是在某些编程语言如Java中,使用特定库(如Jackson、Gson等)将JSON对象或结构转换成JSON字符串的函数。例如,在Java中,如果你有一个`ObjectMapper`实例,你可以这样做: ```java import com.fasterxml.jackson.databind.ObjectMapper; // 假设你有一个Pojo对象 MyClass obj = new MyClass(); ObjectMapper mapper = new ObjectMapper(); String jsonString
recommend-type

JAVA经典算法实战:月兔繁殖与素数判定

在Java编程中,经典算法题目的学习对于提升程序员的逻辑思维和解决问题的能力具有重要意义。以下是从提供的三个Java程序片段中提炼出的关键知识点: 1. 斐波那契数列问题: 题目涉及的是著名的斐波那契数列,它是一个经典的动态规划问题,特点是每一项都是前两项之和。第一个程序展示了如何使用递归方法实现,通过`exp2`类中的`f()`函数计算给定月份数的兔子总数。这里用到了递归公式 `f(x) = f(x-1) + f(x-2)`,该公式对应于序列1, 1, 2, 3, 5, 8, 13, 21...。递归函数设计巧妙地利用了自身调用,减少了重复计算。 2. 素数判断: 第二个程序涉及到判断101-200范围内的素数。素数是只有两个正因数(1和本身)的大于1的自然数。`math`类中的`iszhishu()`函数用于检测一个数是否为素数,它通过检查2到该数平方根之间的整数能否整除该数来判断。这是一种常见的素数检验方法,称为试除法。当找到能整除的因子时,返回`false`,否则如果循环结束都没有找到因子,返回`true`,表示该数是素数。 3. 水仙花数: 第三个程序提到的“水仙花数”是指那些每一位数字的立方和等于其本身的三位数,如153(1^3 + 5^3 + 3^3 = 153)。这里的算法没有直接给出,但提示了寻找这类数的思路,可能是遍历一定范围内的三位数,然后计算各位数字的立方和进行比较。这个题目考察了基本的数学概念和数据结构的使用,比如可能需要用到列表或者集合来存储和验证水仙花数。 这些Java代码示例涵盖了递归、动态规划(如斐波那契数列)、基本的数学逻辑(素数判定)以及简单的数据处理(如查找特定类型的数)。学习这些算法不仅可以提升编程技能,还能培养解决问题的策略,为后续的复杂编程挑战打下坚实的基础。同时,通过实际操作这些代码,程序员可以加深对Java语言特性和控制结构的理解。