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

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

我就废话不多说了，直接上代码吧！

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博客。

展开全文