您现在的位置是:首页 > 正文

Python每日一算法之”最接近k个数”(列表函数运用)

2024-04-01 06:50:07阅读 0
问题描述:

给定一个目标数target,一个非负整数k,一个按照升序排列的数组A。在A中找出与target最接近的k个整数,返回这k个数并按照与target的接近程度从小到大排序,如果接近程度相同,那么值小的排在前面。

问题示例:

如果A=[1,2,3],target=2,k=3,那么返回[2,1,3];

如果A=[1,4,6,8],target=3,k=3,那么返回[4,1,6];

代码实现:

其实就是考场对于python列表的操作,以及在python中列表函数应用。

方法1:利用内置列表操作函数(有时候掌握内置列表操作函数是很重要的)

class Solution:
   def Find_k_closest_num(self,L,cloest,target,k):
      op_list = [x-target for x in L]   #得到与target的差值的列表
      abs_list = [abs(x) for x in op_list]  #取绝对值,获取与target的接近值
      for i in range(k):
         min_num = min(abs_list)    #寻找最接近的
         min_index = abs_list.index(min_num)  #得到最接近的值的索引
         cloest.append(op_list[min_index]+target)  #更新cloest列表
         #分别移除abs_list和op_list中已经添加至cloest的元素
         abs_list.remove(min_num)  
         op_list.pop(min_index)

if __name__ == '__main__':
   mylist = []
   cloest = []
   num = int(input("请输入升序排序列表中元素的个数:"))
   for i in range(num):
      data = int(input("请输入元素:"))
      mylist.append(data)
   target = int(input("请输入目标值:"))
   k = int(input("请输入k值:"))
   temp = Solution()
   temp.Find_k_closest_num(mylist,cloest,target,k)
   print(cloest)

输出:

请输入升序排序列表中元素的个数:3
请输入元素:1
请输入元素:2
请输入元素:3
请输入目标值:2
请输入k值:3
[2, 1, 3]


请输入升序排序列表中元素的个数:4
请输入元素:1
请输入元素:4
请输入元素:6
请输入元素:8
请输入目标值:3
请输入k值:3
[4, 1, 6]

方法2:非内置函数解决

class Solution:
   def kClosestNumbers(self,A,target,k):
      #找到a[left]<target,a[right]>=taeget
      #最接近target的两个数,肯定是相邻的
      right = self.find_upper_closest(A,target)
      left = right - 1
      #两指针从中间向两边扩展,依次找到最接近的k个值
      results = []
      for i in range(k):
         if self.is_left_closer(A,target,left,right):
            results.append(A[left])
            left  -= 1
         else:
            results.append(A[right])
            right +=1
      return results

   def find_upper_closest(self,A,target):
      #找到A中第一个大于等于tatget的数字
      start,end = 0,len(A)-1
      while start+1 < end:
         mid = (start+end)//2
         if A[mid] >= target:
            end = mid
         else:
            start = mid
      if A[start] >= target:
         return start
      if A[end] >= target:
         return end
      return end+1
   
   def is_left_closer(self,A,target,left,right):
      if left<0:
         return False
      if right >=len(A):
         return True
      return target-A[left] <= A[right] - target
   
if __name__ == '__main__':
   mylist = []
   cloest = []
   num = int(input("请输入升序排序列表中元素的个数:"))
   for i in range(num):
      data = int(input("请输入元素:"))
      mylist.append(data)
   target = int(input("请输入目标值:"))
   k = int(input("请输入k值:"))
   temp = Solution()
   cloest = temp.kClosestNumbers(mylist,target,k)
   print(cloest)

输出:

请输入升序排序列表中元素的个数:3
请输入元素:1
请输入元素:2
请输入元素:3
请输入目标值:2
请输入k值:3
[2, 1, 3]


请输入升序排序列表中元素的个数:4
请输入元素:1
请输入元素:4
请输入元素:6
请输入元素:8
请输入目标值:3
请输入k值:3
[4, 1, 6]

网站文章

  • 红米hm2a显示无法连接到服务器,红米HM2A刷机教程

    红米hm2a显示无法连接到服务器,红米HM2A刷机教程

    红米刷机教程刷机教程方法1:系统内升级下载必要的文件,为刷机过程做准备。MIUI完整包跨版本升级、降级均需手动进入Recovery 清除全部数据。下载 MIUI_ROM 最新安装包 立即下载如果已经在...

    2024-04-01 06:49:28
  • 知名大厂的18道Android面试题曝光,你能回答几道?

    知名大厂的18道Android面试题曝光,你能回答几道?

    最近一位知名大厂的Android技术主管,跟我透露了他们公司的18道超难的Android面试题,有些题小编看了都觉得很刁钻。今天小编给大家来做个剧透,你也可以对应看一下,你能回答出来几题?下面有面试题...

    2024-04-01 06:49:22
  • 第三方登陆html,第三方登录流程.html

    第三方登陆html,第三方登录流程.html

    第三方登录流程$axure.utils.getTransparentGifPath = function() { return 'resources/images/transparent.gif';...

    2024-04-01 06:49:14
  • Windows环境下使用Nexus-3.16x版本构建Maven私有仓库

    Windows环境下使用Nexus-3.16x版本构建Maven私有仓库

    一、Nexus的下载与安装下载Nexus官方下载地址:https://www.sonatype.com/download-oss-sonatype安装1. 安装环境:系统环境:Windows10 JDK版本:1.8.0_11 Maven版本:3.3.9 Nexus版本:3.16.0-012. 安装步骤:① 解压下载好的Nexus,截图如下:根目录...

    2024-04-01 06:49:07
  • pdf.js 使用实例

    pdf.js 使用实例

    https://www.cnblogs.com/xiangliuyunyang/p/5956453.html pdf.js可以实现在html下直接浏览pdf文档,是一款开源的pdf文档读取解析插件 pdf.js主要包含两个库文件,一个pdf.js和一个pdf.worker.js,,一个负责API解析,一个负责核心解析 下载地址:http://cnblogs.com/files/...

    2024-04-01 06:48:21
  • 【序列推荐】CIKM2020|S3---基于自监督学习的序列推荐模型

    【序列推荐】CIKM2020|S3---基于自监督学习的序列推荐模型

    前言文章发表在2020年CIKM会议上,与以往分享的端到端的模型不同,文章基于互信息最大化(mutual information maximization)原则,提出了一个自监督的序列推...

    2024-04-01 06:48:13
  • 服务器访问系统盘 数据盘,云服务器系统盘数据盘

    服务器访问系统盘 数据盘,云服务器系统盘数据盘

    云服务器系统盘数据盘 内容精选换一换当服务器中的磁盘发生故障、或者由于人为误操作导致服务器数据丢失时,可以使用已经创建成功的备份恢复服务器。云服务器备份仅支持将服务器中的所有云硬盘作为整体进行备份和恢...

    2024-04-01 06:47:28
  • 用动态规划方法求解0-1背包问题

    如果你对动态规划方法求解0-1背包问题的思路不清晰,直接阅读代码并不是一个好的建议。推荐一个B站up主的视频讲解:0/1背包问题-动态规划练习地址(B站视频配套的网址)#include<iostrea...

    2024-04-01 06:47:21
  • IOS Object和javaScript相互调用

    在IOS开发中有时会用到Object和javaScript相互调用,具体步骤如下:1. Object中执行javascript代码,这个比较简单,苹果提供了很好的方法- (NSString *)stringByEvaluatingJavaScriptFromString:(NSString *)script2. javascript执行过程中返回给Object的数据或者调用Obje

    2024-04-01 06:47:15
  • html的浮动作用是什么意思,html中浮动是什么

    html的浮动作用是什么意思,html中浮动是什么

    在HTML中,浮动就是让元素可以向左或向右移动,直到它的外边距碰到其父级的内边距或者是上一个元素的外边距,只需要给元素设置“float:left|right|none|inherit”样式即可。本教程操作环境:windows7系统、CSS3&&HTML5版、Dell G3电脑。一.什么是浮动(float)?浮动就是让元素可以向左或向右移动,直到它的外边距碰到其父级的内边距或者是上一...

    2024-04-01 06:46:33