首页 > python教程

在python3中实现查找数组中最接近与某值的元素操作

时间:2020-08-12 python教程 查看: 1654

我就废话不多说了,直接上代码吧!

import datetime

def find_close(arr, e):
 start_time = datetime.datetime.now()

 size = len(arr)
 idx = 0
 val = abs(e - arr[idx])

 for i in range(1, size):
  val1 = abs(e - arr[i])
  if val1 < val:
   idx = i
   val = val1

 use_time = datetime.datetime.now() - start_time

 return arr[idx], use_time.seconds * 1000 + use_time.microseconds / 1000

def find_close_fast(arr, e):
 start_time = datetime.datetime.now()

 low = 0
 high = len(arr) - 1
 idx = -1

 while low <= high:
  mid = int((low + high) / 2)
  if e == arr[mid] or mid == low:
   idx = mid
   break
  elif e > arr[mid]:
   low = mid
  elif e < arr[mid]:
   high = mid

 if idx + 1 < len(arr) and abs(e - arr[idx]) > abs(e - arr[idx + 1]):
  idx += 1

 use_time = datetime.datetime.now() - start_time

 return arr[idx], use_time.seconds * 1000 + use_time.microseconds / 1000

if __name__ == "__main__":
 arr = []

 f = open("1Mints.txt")
 for line in f:
  arr.append(int(line))
 f.close()

 arr.sort()

 while 1:
  e = int(input("input a number:"))
  print("find_close ", find_close(arr, e))
  print ("find_close_fast ", find_close_fast(arr, e))

补充拓展:查询集合中最接近某个数的数

查询集合中最接近某个数的数

/*
★实验任务
给你一个集合,一开始是个空集,有如下两种操作:

向集合中插入一个元素。
询问集合中最接近某个数的数是多少。
★数据输入
输入第一行为一个正整数 N,表示共有 N 个操作。
接下来 N 行,每行一个操作。
对于第一个操作,输入格式为 1 x,表示往集合里插入一个值为 x 的元素。
对于第二个操作,输入格式为 2 x,表示询问集合中最接近 x 的元素是什么。
1<=N<=100000,1<=x<=1000000000。

★数据输出
对于所有的第二个操作,输出一个或者两个整数,表示最接近 x 的元素,有
两个数的情况,按照升序输出,并用一个空格隔开。
如果集合为空,输出一行“Empty!”
数据保证插入的元素两两不同。

输入示例 输出示例

5 Empty!
2 1 2
1 2 2 4
2 3
1 4
2 3
*/

解题思路

一、采用C++ 中map容器,因为它可以实时对输入的元素进行排序。(map的使用可自行百度)

二、当集合为空时,输出“Empty!”;当集合中只有一个元素时,直接输出该元素。

三、下面重点看一般的情况。

1.先查找集合中是否有查询的元素,有则输出该元素

2.没有的话,将该元素先插入集合中,再查找该元素处于集合的某个位置。

若该元素在集合的首位,则输出该数的下一位。

若该元素在集合的末位,则输出该数的上一位。

否则,判断它左右元素的值与它的差的绝对值,输出差的绝对值较小的那个元素。若相等,则同时输出。

#include <iostream>
#include <map>
#include <cmath> 
using namespace std;
map <long long ,int> a;
int main()
{
a.clear() ;
int N,t;
long long int x;
cin >> N;
while(N--)
{
cin >> t >> x;
if(t==1)
a[x]=1;
else
{
if(a.empty() )//判断集合是否为空 
cout << "Empty!\n" ;
else
{
if(a.size() == 1 )//若只有一个元素,则直接输出 
cout << a.begin()->first << endl;
else
{
map <long long ,int>::iterator it,m,n;
it=a.find(x);
if(it!=a.end() )
{
cout << x <<endl;
continue;
}
a[x]=1;
it=a.find(x);
if(it == a.begin() )
{
it++;
cout << it -> first << endl;
} 
else if(it == a.end() )
{
it--;
cout << it -> first << endl; 
}
else
{
m=--it;//m和n分别指向it的左右两侧 
it++;
n=++it;
if(abs(m -> first - x) > abs(n -> first - x))
cout << n -> first << endl;
else if(abs(m -> first - x) == abs(n -> first - x))
cout << m -> first << " " << n -> first << endl;
else
cout << m -> first << endl;
}
a.erase(a.find(x) ); 
} 
}
}
}
return 0;
}

以上这篇在python3中实现查找数组中最接近与某值的元素操作就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持python博客。

展开全文
上一篇:python 已知一个字符,在一个list中找出近似值或相似值实现模糊匹配
下一篇:python GUI库图形界面开发之PyQt5选项卡控件QTabWidget详细使用方法与实例
输入字:
相关知识
Python 实现图片色彩转换案例

我们在看动漫、影视作品中,当人物在回忆过程中,体现出来的画面一般都是黑白或者褐色的。本文将提供将图片色彩转为黑白或者褐色风格的案例详解,感兴趣的小伙伴可以了解一下。

python初学定义函数

这篇文章主要为大家介绍了python的定义函数,具有一定的参考价值,感兴趣的小伙伴们可以参考一下,希望能够给你带来帮助,希望能够给你带来帮助

图文详解Python如何导入自己编写的py文件

有时候自己写了一个py文件,想要把它导入到另一个py文件里面,所以下面这篇文章主要给大家介绍了关于Python如何导入自己编写的py文件的相关资料,需要的朋友可以参考下

python二分法查找实例代码

二分算法是一种效率比较高的查找算法,其输入的是一个有序的元素列表,如果查找元素包含在列表中,二分查找返回其位置,否则返回NONE,下面这篇文章主要给大家介绍了关于python二分法查找的相关资料,需要的朋友可以参考下