从1到100 000 中任意拿掉两个数字,把剩下的99998个数顺序打乱,并且放入数组A中。要求只扫描一遍,把这两个数找出来;可以使用最多不超过5个局部变量,不能使用数组变量,并且不能改变原数组的值。
package com.java.examples.digui;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashSet;
/**
* 从1到100 000 中任意拿掉两个数字,把剩下的99998个数顺序打乱,并且放入数组A中。
* 要求只扫描一遍,把这两个数找出来;可以使用最多不超过5个局部变量,不能使用数组变量,并且不能改变原数组的值。
*
* @author yuahan
*
*/
public class FindMissing2Numbers {
/**
* 大数的开方运算
* @param theNumber
* @return
*/
private static BigInteger sqrt(String theNumber) {
int length = theNumber.length(), i;
BigInteger res = BigInteger.ZERO;
BigInteger twenty = BigInteger.valueOf(20);
BigInteger t, x = BigInteger.ZERO, v, few = BigInteger.ZERO;
BigInteger hg = BigInteger.valueOf(100);
String tmpString = null;
int pos = 2 - length % 2;
tmpString = theNumber.substring(0, pos);
while (true) {
v = few.multiply(hg).add(BigInteger.valueOf(Integer.parseInt(tmpString)));
if (res.compareTo(BigInteger.ZERO) == 0)
i = 9;
else
i = v.divide(res.multiply(twenty)).intValue();
for (; i >= 0; i--) {
t = res.multiply(twenty).add(BigInteger.valueOf(i)).multiply(BigInteger.valueOf(i));
if (t.compareTo(v) <= 0) {
x = t;
break;
}
}
res = res.multiply(BigInteger.TEN).add(BigInteger.valueOf(i));
few = v.subtract(x);
pos++;
if (pos > length)
break;
tmpString = theNumber.substring(pos - 1, ++pos);
}
return res;
}
/**
* 逐一比较。但是这个不满足要求。不止一次的扫描数组。
* @param array
*/
public static void test1(int[] array){
Arrays.sort(array);
int off = 1;
for(int i=1;i<=(array.length + 2);i++){
int index = i - off;
if(index >= array.length){
index = array.length - 1;
}
if(i - array[index] != 0){
System.out.println(i);
off++;
continue;
}
}
}
/**
* 在大概40000左右的时候,经过几十秒的时间可以找到,但是更大的时候便不准确。可能是由于sqrt非常非常大的数的时候出现的问题。
* 用到了数学中的这个原理:
* a + b = he
* a * b = ji
* 通过方程组转变成一元二次方程来解a 和 b。
* @param array
*/
public static void test2(int[] array){
BigInteger he = BigInteger.ZERO;
BigInteger ji = BigInteger.ONE;
BigInteger he_array = BigInteger.ZERO;
BigInteger ji_array = BigInteger.ONE;
he = new BigInteger(((array.length + 2) * (array.length + 3) / 2) + "");
for (int i = 1; i <= array.length + 2; i++) {
ji = ji.multiply(new BigInteger(String.valueOf(i)));
}
for (int i = 0; i < array.length; i++) {
he_array = he_array.add(new BigInteger(String.valueOf(array[i])));
ji_array = ji_array.multiply(new BigInteger(String.valueOf(array[i])));
}
he = he.subtract(he_array);
ji = ji.divide(ji_array);
BigInteger temp = sqrt(he.pow(2).subtract(ji.multiply(new BigInteger("4"))).toString());
;
System.out.println((he.add(temp)).divide(new BigInteger("2")));
System.out.println((he.subtract(temp)).divide(new BigInteger("2")));
}
/**
* 正确的方法。简单,快速。
* @param array
*/
public static void test3(int[] array){
HashSet<Integer> set = new HashSet<Integer>(array.length);
for(int i : array){
set.add(i);
}
for(int i=1;i<=(array.length + 2);i++){
if(!set.contains(i)){
System.out.println(i);
}
}
}
public static void main(String[] args) {
// int[] array = {1,2,3,4,5,6,7,8,9,10,11,12,13};
// test3(array);
}
}
分享到:
相关推荐
### 9个步骤恢复格式化数据、删除数据与丢失数据 #### 一、引言 在数字时代,数据丢失已成为用户普遍面临的问题之一。无论是由于误操作还是硬件故障导致的数据丢失,都可能对个人或企业造成严重影响。因此,掌握...
2. **预览功能**:在恢复文件之前,用户通常可以预览找到的文件内容,确保它们是需要恢复的目标文件,避免盲目恢复导致的错误。 3. **支持多种文件类型**:高质量的恢复软件能支持恢复各种类型的文件,如文档、图片...
为了解决这个问题,开发者可以利用Web Storage API中的localStorage功能来存储临时数据,防止页面刷新后数据丢失。 ### localStorage简介 localStorage是Web Storage API的一部分,它提供了一种在客户端浏览器存储...
在IT领域,数据丢失是一个常见的问题,尤其是在存储设备如硬盘、SSD或USB驱动器上。当分区丢失时,这可能会导致用户无法访问存储在该分区上的文件和数据。本篇将详细介绍分区丢失的数据恢复方法,并提供一些实用的...
1. **分区恢复**:当EF盘或其他分区意外消失时,该软件能扫描硬盘,找到丢失的分区信息,并尝试恢复其结构和数据。 2. **数据恢复**:即使分区丢失,软件也能深入硬盘扇区,查找并恢复未被覆盖的数据,包括文档、...
在数据库管理领域,SQL并行更新是一个常见的性能优化策略,特别是在处理大数据量或者复杂查询时。然而,这种并行执行模式也可能带来数据一致性问题,如标题所提的“SQL并行更新时丢失数据实例”。本篇文章将深入探讨...
本项目名为"C实现因格式化而丢失数据的恢复",它提供了一个Unformat程序,专门针对这种情况,帮助用户找回被格式化的数据。这个程序的亮点在于它支持超过200GB的大硬盘,这在当今大数据的时代显得尤为重要。 首先,...
在IT领域,数据恢复是一项至关重要的技能,尤其是在遭遇意外情况如系统还原或分区合并后导致的数据丢失。本文将详细介绍一种针对“还原系统分区合并数据丢失”的恢复方法。 首先,问题的起因是用户使用系统自带的...
正好公司运行程序又全在那个分区,悲催的搞了2天,还好找到了这个软件,恢复的数据还能用,不然悲催了,哈哈~~装了服务器系统的兄弟如果丢失分区了,建议拷回去试试,不过恢复数据都是看rp的,还是平时勤快点的好
2. **网络传输问题**:在网络不稳定时,大数据量的传输可能会导致部分数据丢失。确保网络环境稳定,并使用可靠的传输机制。 3. **编码格式不一致**:客户端和服务器之间编码格式不匹配可能导致数据乱码,从而看似...
因此,在新的数据覆盖这些位置之前,数据恢复工具可以找到并恢复这些未被覆盖的原始数据。 "超级数据恢复"可能采用了深度扫描和文件预览功能。深度扫描能够逐扇区扫描整个硬盘,寻找已被删除文件的痕迹;而文件预览...
在这个过程中,关键的步骤包括分析存储介质(如硬盘、闪存驱动器等),识别文件系统结构,定位丢失的文件片段,并尝试重组这些片段以恢复原始数据。 在C/C++中实现数据恢复,需要掌握以下几个核心知识点: 1. **...
2. **“深度扫描”**:当常规扫描无法找到丢失的文件时,深度扫描会进行全面的扇区级扫描,虽然耗时较长,但能发现更多可能丢失的文件。 3. **“分区恢复”**:如果你的分区出现错误或被格式化,这个选项可以帮助你...
金山数据恢复大师是一款专业的数据恢复软件,用于帮助用户找回意外丢失的文件。下面将详细介绍如何使用这款工具来恢复丢失的数据。 首先,恢复丢失数据的第一步是下载并安装金山数据恢复大师。用户可以从官方渠道...
### 重装系统分区丢失只剩一个盘的数据恢复方法 #### 背景介绍 在进行系统重装过程中,用户可能会因为误操作导致原本存在的多个分区(如D、E、F等)仅剩下一个分区(通常是C盘),这不仅会导致原有分区的结构丢失,...
因此,要想恢复丢失分区中存放的数据,可以采取使用十六进制编辑器手动分析硬盘中数据信息的方式,直接找到丢失分区中存放数据的区域,然后对丢失分区中存放的重要数据进行恢复。 MiniTool 数据恢复工具为大家提供...
2. 数据库使用回滚段中的信息构建一个只读的旧数据视图。 3. 用户检查这个视图,找到误操作的数据。 4. 用户根据需要进行恢复,如重新插入删除的记录。 在实际应用中,闪回功能在多个场景下都发挥了重要作用,例如...
数据恢复技术是信息技术领域中的一个重要分支,它涉及到对丢失、损坏或不可访问的数据进行恢复,以便重新获得对这些数据的访问。在这个深度揭秘的过程中,我们将探讨数据恢复的关键概念、技术方法以及常见应用场景。...
2. **停止写入新数据**:避免向出现问题的硬盘写入新的数据,因为新写入的数据可能会覆盖已丢失的数据,从而降低数据恢复的成功率。 3. **选择合适的数据恢复软件**:使用可靠且功能强大的数据恢复软件是成功恢复...
数据恢复在IT行业中是一项至关重要的技术,特别是在个人和企业用户面临意外数据丢失时。"数据恢复医生"就是这样的工具,能够帮助用户找回那些被误删除的文件,避免因数据丢失造成的损失。标题和描述中提到的功能表明...