据传说是MS/Google等等IT名企业的面试题:
有一组数字,从1到n,中减少了一个数,顺序也被打乱,放在一个n-1的数组里
请找出丢失的数字,最好能有程序,最好算法比较快
假如有1,2,3,···,10十个数字,并且少了5,那么遍历数组求和得到50,在遍历的过程中得知最大数字为10,那么如果不少5,全部数字和为55,则缺少的数字为55-50=5
如果少了10,那么遍历数组得到的和为45,最大数字为9,和依然为45,45-45=0,则丢失的数字为9+1=10
或者就是申请n-1个空间,遍历标记!
import java.util.Arrays;
import java.util.Random;
public class FindLostNumber {
public static int findLostNumber(int[] Data){
int sum = 0;
int max = 0;
int total = 0;
for(int i=0; i<Data.length; i++){
if(Data[i]>max){
max = Data[i];
}
sum += Data[i];
}
total=(max*(max+1))/2;
int lost = total-sum;
if(lost>0){
return lost;
}else{
return max+1;
}
}
public static void main(String[] args){
Random random = new Random();
int lost = random.nextInt(4999)+1;
System.out.println("I lost "+lost);
int[] elements = new int[5001];
//第一种方法
int index = 0;
for(int i=1; i<=5000; i++){
if(i==lost){
continue;
}
elements[index++] = i;
}
int find = findLostNumber(elements);
System.out.println("I find you lose "+find);
//第二种方法
boolean[] mark = new boolean[5001];
Arrays.fill(mark, false);
for(int i=0; i<elements.length; i++){
mark[elements[i]] = true;
}
for(int i=1; i<mark.length; i++){
if(!mark[i]){
System.out.println("You lost "+i);
}
}
}
}
分享到:
相关推荐
因此,主要任务是从这些设备中检索被盗或丢失的数据。 数字取证以系统和有效的方式为这种数据提取提供了准确的概念。 现在,损坏的数字存储设备可能有各种情况,例如可能被烧毁、潮湿或物理损坏的部件,所有这些...
注意:如果您遗失了本软件,请在互联网上寻找SHA512加密,对您的密码主体 识别码进行【三次】加密(也就是用第一次的加密结果进行第二次加密,第二次的结果进行第三次加密,注意!每次结果取大写!),然后对第...
丢失的最小正整数leetcode LeetCode leetcode 题目(共 65 题) 1 两数之和 2 两数相加 3 无重复字符的最长子串 4 寻找两个正序数组的中位数 7 整数反转 9 回文数 13 罗马数字转整数 14 最长公共前缀 15 三数之和 16 ...
实现了即时发布消息,支持基本寻物信息与招领信息的发布,支持上传物品图片,而且可以在百度地图上标注物品丢失或捡到的具体位置,将极大地满足用户的需求,提高找回失物的概率。失物招领平台,致力于提供方便、快捷的寻物...
软件自带密码生成工具,可以选择纯数字,纯字母,字母数字混合各种模式。 本软件数据库可以在苹果,安卓手机平台上使用,数据多种平台兼容。 软件使用开源数据库,并可导出导入CVS文本,增强了信息的交换性,防止...
如果用了很多数据恢复软件,都不能找到你的丢失的数据分区,B计划数据恢复软件一定要试下,它超过国外知名的软件的恢复速度,以及找回数据的能力。 B计划数据恢复软件功能: 1、B计划数据恢复软件运行于...
遗失信件 排序联盟 转换HTML实体 将所有奇数斐波那契数字相加 求所有素数 最小公倍数 算了吧 压路机 二元代理 一切都是真实的 参数可选 做一个人 映射碎片 JavaScript算法和数据结构项目 回文检查器 ...
10S管理理念 将寻找物品时间缩短为零 达到的效果 有丢失、损坏可以立即发现 不同人员操作效果一样 明确标示以便清晰分辨 15 10S管理培训-精品培训资料全文共48页,当前为第15页。 整顿前 整顿之后效果 10S管理培训-...
据外媒报道,美国专利商标局日前授予苹果一项名为“失物招领服务中电源管理”的专利,这项专利能够通过数字定位技术帮助用户更快找回丢失的物品。
只要你有routers的配置文件,本软件可以帮助你找回丢失了的Cisco密码 限于password 7 type ,速度快得惊人,我有一个密码里面包含..+字母+数字,一秒不到!
WinHex的内存搜索编辑功能可以帮我们找回丢失的还原精灵密码。具体方法是:右击任务栏右下角的还原精灵图标,在弹出菜单中选择“参数设置→更改密码”,在对话框中输入旧密码,胡乱填写几个数字如123456;在新密码框...
她可以保存,但是不会再占用您书架的空间,不会沾满尘土又担心难以寻找,更妙的是,即使丢失或无意中损坏,您仍然可以随意获得。她是 Zubu ,突破了传统的平面阅读模式,引领你到另一个不同的阅读空间。 Zubu ...
通过这个系统,学生和教职工可以方便地报告失物信息,寻找丢失的物品,同时也为捡到物品的人提供一个便捷的归还渠道。 主要功能包括: 1. **失物信息发布**:用户可以在小程序中发布失物信息,包括物品描述、丢失...
实际只有139个,其余部分丢失! 第一部分 基础篇 001 第一个C程序 002 运行多个源文件 003 求整数之积 004 比较实数大小 005 字符的输出 006 显示变量所占字节数 007 自增/自减运算 008 数列求和 009 乘法...
倒水leetcode 代码挑战 我的个人编码脑筋急转弯集 :collision: 8/9/2018 - 字转换 将 wordA ...空间中找到丢失的数字? 如果缺少两个数字怎么办? 7/13/2018 - 中值堆 获取数组的中位数 (例如)给定[1
另外该版本收集了很多现在有模板,不用你再花费时间去寻找了。 这是网上收集的介绍: WinHex 是一款以通用的 16 进制编辑器为核心,专门用来对付计算机取证、数据恢复、低级数据处理、以及 IT 安全性、各种日常紧急...
Secret 可以本地备份及邮箱备份,数据不会丢失 Secret 操作简单,功能简单 ## Secret的缺点 Secret 本身的账号密码以及加密数字,需要用户记住,否则无法找回 ## 运行 1.启动程序 /bin/secret.bat 2....
解决纠纷 防盗、寻找失物。通过调用物品丢失过程的图像资料。 通过与报警系统联动(视频服务器配置了3个报警输入1个报警输出支持开关量和脉 冲),如有非法入侵的情况,探测器将报警信号送给视频服务器,在监控中心...
leetcode ...寻找丢失的数 II) 2. Linked List:单?双?环? 3. Array 形态:升序,降序,反转(怎么个转法) 值:重复?特殊值(空串) 4. Tree 树的类型,类型的定义(e.g. BST是否存在相等节点
赶快行动吧,使用我们的文件恢复软件,去找回您珍贵的回忆纪念!产品功能功能说明* 硬盘驱动器已被格式化; * 损坏或丢失重要的文件系统结构; * 意外的文件删除; * 不明原因的文件丢失; * 系统意外关机或应用...