请实现以下算法，语言不限，也可以是伪代码。
1.有一个数组 a[1000]存放了1000 个整数，这 1000个数都大于等于1，小于等于999, 并且只有两个数是相同的（假设该数为a）,
剩下的 998个数均不相同。请写一个最优搜索算法，找出a，并给出该算法的时间复杂度。
/**
* @author wangjin
* @title: SearchNumber
* @projectName
* @description: 时间复杂度为O()=O(logn)
* @date 2022/4/18 0018 16:33
*/
public class SearchNumber {
//被搜索数据的大小
private static final int size=1000;
public static void main(String[] args) {
//添加测试数据
int[] data=new int[size];
for (int i = 0; i <data.length ; i++) {
data[i]=i+1;
}
data[999]=62;
result(data);
}
public static void result(int data[]){
//排序
Arrays.sort(data);
for (int i=0;i<data.length;i++){
int target =data[i];
data[i]=0;
int result =binaryFind(data,target);
if(result !=-1){
System.out.println("相同元素为："+data[result]);
break;
}
}
}
/**
* @Author wangjin
* @Description //二分搜索算法实现
* @Date 2022/4/18 0018
* @Param [data, target] 数据集合，搜索的数据
* @return int 返回找到的数据的位置，返回-1表示没有找到
**/
public static int binaryFind(int[] data, int target) {
int satrt =0;
int end=data.length-1;
while (satrt <=end){
int middle=(satrt+end) /2;
if(target ==data[middle]){
return middle;
}
if(target >=data[middle]){
satrt =middle+1;
}else{
end=middle-1;
}
}
return -1;
}
}
2.给出任意正整数X（X 小于 2的31次幂）, 求不比X小且是2的整数次幂中最小的值Y。例如X=7，则Y为8；X=8，则Y为8。
package com.taotao.wifepojie.test;
import java.math.BigInteger;
/**
* @author wangjin
* @title: Exponentiation
* @projectName wife-pojie
* @description: TODO
* @date 2022/4/18 0018 17:37
*/
public class Exponentiation {
public static void main(String[] args) {
//X 小于 2的31次幂
int X=7;
BigInteger pow = BigInteger.valueOf(2).pow(31);
BigInteger bigInteger = BigInteger.valueOf(Integer.valueOf(X));
if(bigInteger.compareTo(pow)==-1){
System.out.println(highestOneBit(X));
}
}
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
int j= i - (i >>> 1);
return j*2;
}
}
3.现有一个数据文件data.csv，里面有1000万条时序数据（按时间升序），共两列，第1列为时间（日期时间类型，到秒），
第2列为值（单精度类型）。请输出每分钟的平均值。
数据格式如下：
2017\8\6 5:13:55,802.43
2017\8\6 5:13:56,803.537
2017\8\6 5:13:58,803.638
2017\8\6 5:14:00,803.238
2017\8\6 5:14:01,803.142
2017\8\6 5:14:02,803.1453
2017\8\6 5:14:03,803.1486
2017\8\6 5:14:04,803.152
2017\8\6 5:14:05,803.1553
2017\8\6 5:14:06,803.1586
2017\8\6 5:14:17,803.1619
2017\8\6 5:14:18,803.1652
select minute_time 时间,avg(data) 平均值
from
(select
substring(time,1,16)as minute_time ,
data
from test2 ) tmp
group by minute_time
结果截图：
image.png
4.请写一个程序，输出2的10000次方的值。
方法1：
package com.taotao.wifepojie.test;
import org.springframework.util.CollectionUtils;
import java.util.LinkedList;
import java.util.List;
public class CalculateTheSquare {
/**
* 用数组计算2^10000
* @param args 计算平方
*
*/
public static void main(String[] args) {
//数组存储每一位的数字
List<Integer> num= new LinkedList<>();
for(int i=1;i<=10000;i++){
if(CollectionUtils.isEmpty(num)){
num.add(2);//设置初始值
}else {
int inc=0;//进位数，初始为0
for(int j=0;j<num.size();j++){
int multi= num.get(j)*2;//对应位数上乘以2
int forward=(multi+inc)/10;//获取下次进位数
int data=(multi+inc)%10;//进位数和结果相加，获取个位数
num.set(j,data);//替换原来对应位置上的数字
inc=forward;
}
//如果进位数大于零，那么进位数需要加入链表，进行下次计算
if(inc>0){
num.add(inc);
}
}
}
/**
* 打印结果
*/
for(int k=num.size()-1;k>=0;k--){
System.out.print(num.get(k));
if(k==0){
System.out.println("\n");
}
}
}
}
方法2：
package com.taotao.wifepojie.test;
import java.math.BigInteger;
/**
* @author wangjin
* @title: CalculateTheSquare1
* @projectName wife-pojie
* @description: TODO
* @date 2022/4/18 0018 17:22
*/
public class CalculateTheSquare1 {
public static void main(String[] args) {
//计算2^10000
BigInteger pow = BigInteger.valueOf(2).pow(10000);
System.out.println(pow);
}
}
输出结果:
19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376
网友评论