目录
推荐公众号问题场景思路代码
推荐公众号
有彩蛋哦!!!(或者公众号内点击网赚获取彩蛋)
问题场景
今天同事问了一个问题，如何在一个集合中取一个最接近某个数的数，脑海各种算法(背包，图论，动态规划)在飘，让我回想起了大二ACM算法竞赛期间的生活。ACM真的是让我又爱又恨；爱，当你掌握一种算法AC出题目的时候是真的爽；恨，算法是真的难理解；当时还想着打游戏，打篮球，兼职赚钱，一直没有认真系统的学习算法导致一知半解，参加竞赛也没有获得好名次，现在再提起算法就忘的一干二净了，真是书到用时方恨少啊。
思路
将集合排除，剔除重复数据，二分查找，向差值小的方向移动 不知道是否还有更好的思路，请指教
代码
public static void main(String
[] args
) {
Integer c
= 0;
Integer
[] number
= {2, 4,6,7,12,45,67,90};
System
.out
.println(find(number
, 0, number
.length
-1, 1, c
));
}
public static Integer
find(Integer
[] number
, Integer start
, Integer end
, Integer k
, Integer c
){
c
++;
System
.out
.println("次数"+c
);
if (start
== end
){
return number
[start
];
}
if (Math
.abs(start
-end
) == 1){
Integer startN
= number
[start
];
Integer endN
= number
[end
];
int startSub
= Math
.abs(startN
- k
);
int endSub
= Math
.abs(endN
- k
);
return startSub
< endSub
? startN
: endN
;
}
int midle
= (start
+ end
)/2;
Integer left
=number
[midle
-1];
Integer right
= number
[midle
+1];
int rightSub
= Math
.abs(right
- k
);
int leftSub
= Math
.abs(left
- k
);
if (leftSub
< rightSub
){
return find(number
, start
, midle
- 1, k
, c
);
}
if (rightSub
< leftSub
){
return find(number
, midle
+ 1, end
, k
, c
);
}
return 1;
}
