获取不连续数字中缺的数字
获取不连续数字中缺的数字
袁新栋-jeff.yuan
发布于 2021-02-04 10:30:32
发布于 2021-02-04 10:30:32
背景
最近项目需求需要做一个档案管理系统，其中一个功能就是判断凭证是否断号。且将断号的号码找出来。
需求分析
- 凭证的短号规则，也就是这个凭证是通过怎么一个规则来判断短号的。最后和产品了解每个公司都有自己的规则。不一定是纯数字，也有可能标记有横杠特殊字符等。
- 砍需求，由于我们在年底进行开发的版本是POC版本，并且时间非常的紧急（以至于我们每天都要搞到11点）。所以说不用很复杂的业务需求，所以最后讨论下来先做为写死的纯数字校验。 所以有了今天这篇文章。
CODOING
- 其实有很多同学看到这个一串数字断号校验，这有什么可讲的呢？简单的一批。
- 刚开始的思路：这些数字有可能从零开始，也有可能从一开始，也有可能从。也有可能中间有很多断号的等等。。。。有很多种情况。那就先拿出第一个短号的数据试试。
- 时间复杂度为O(n)
/**
* 判断短号
*
* @param nos 凭证号
* @return -> 第一各所断的号
*/
Long isBreak(List<Long> nos) {
//边界判断
if (nos.size() <= 1) {
return null;
}
//先进行一次排序
List<Long> sortList = nos.stream().sorted(Comparator.comparing(t -> t)).collect(Collectors.toList());
//第一个数+1与第二个数+1否相等，相等则OK，不等则有问题。
for (int i = 0; i < nos.size()-1; ++i) {
if (sortList.get(i) + 1 != sortList.get(i+1)) {
return sortList.get(i) + 1;
}
}
return null;
}- 但是这样不能完全满足产品的需求，那我们得再开动开动脑筋出个2.0版本。
/**
* 判断短号
*
* @param nos 凭证号
* @return ->
*/
List<Long> isBreak(List<Long> nos) {
final Object[] objects = nos.toArray();
Arrays.sort(objects);
int length = objects.length;
Integer max = (Integer) objects[length - 1];
ArrayList<Long> integers = Lists.newArrayList();
//将所有的值从第一个数字生成
for (long min = (long) objects[0]; min <= max; min++) {
integers.add(min);
}
//返回缺失的数字
return integers.stream().filter(t -> !nos.contains(t)).collect(Collectors.toList());
}- 看似是没什么问题，就在这个时候，出问题了。测试同学说怎么经常报错呢？直接功能全部用不了， 于是看了下后台直接机器重启了，大概推测一下就是OOM了，导致机器重启了。于是我大概看了下，看到他搞了两个差了好几亿的凭证号执行了操作。这肯定是是死翘翘了
- 那我们再优化一下：
/**
* 判断短号
*
* @param nos 凭证号
* @return ->
*/
List<Long> isBreak(List<Long> nos) {
final Object[] objects = nos.toArray();
Arrays.sort(objects);
int length = objects.length;
Integer max = (Integer) objects[length - 1];
Integer min = objects.get(0);
//如果最大了和最小的大于100个短号那就采用只获取第一个短号
if(max - min > 100){
for (int i = 0; i < nos.size()-1; ++i){
if (sortList.get(i) + 1 !=sortList.get(i+1)) {
return Arrays.asList(sortList.get(i) + 1);
}
}
return null;
}
ArrayList<Long> integers = Lists.newArrayList();
//将所有的值从第一个数字生成
for (long min = (long) objects[0]; min <= max; min++) {
integers.add(min);
}
//返回缺失的数字
return integers.stream().filter(t -> !nos.contains(t)).collect(Collectors.toList());
}总结
- 问题简单划，思维多元化，多个角度看问题
- 很多时候我们的打错都是出现在小问题上，所以不能轻易藐视任何一个问题。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-01-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录