昨天参加一个1.5K-2.5K的笔试，碰到一题目，大致如下：有一个长度为998的数组，里面是1-1000并且无重复的数。只用一次遍历，不能使用集合，算出1-1000不在这个数组中的那2个数。
------解决方案--------------------
可以用移除已有的这种手段
------解决方案--------------------
哥的回复哪去了？
------解决方案--------------------
这1.5K-2.5K是薪水吗？太坑爹了吧
------解决方案--------------------
这个。。。。。。。。。。。
------解决方案--------------------
------解决方案--------------------
先求出2个数的和和乘积然后解方程
------解决方案--------------------
创建一个1-1000的有序数组 索引是0的为1 索引是1的value为2以此类推。
遍历已知数组A 将A中的值与有序数组进行比较 命中有序数组的索引将其value设置为-1.这样遍历之后有序数组value不为-1的为没有的两个数字。
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
n(n+1)(2n+1)/6
计算出1到1000的平方和
------解决方案--------------------
- Java code
int[] a = new int[]{2,4,3,9,6,7,5,1}; Arrays.sort(a); int count = 0; int k=1; for(int i=0;i<8;){ if(k==a[i]){ k++; i++; }else{ System.out.print(k+" "); count++; k++; } } //System.out.print(count); if(count==0){ System.out.println("9 10"); } else if(count==1){ System.out.println(" 10"); }
------解决方案--------------------
- Java code
int[] a = new int[998]; //要查找的数组int[] b = new int[1000]; //下标累加for (int i : a) { b[i]++;}for (int i=0; i<b.length; i++) { //如果1000的循环不算，可以采用数组下标累加 if (b[i] == 0) { System.out.println(i); }}
------解决方案--------------------
设置一个数组将有一个长度为998的数组和1-1000的数字合并，然后再在这个新的数组里去除相同的元素，剩下的就是你要找的那两个数
------解决方案--------------------
可以自己写个集合类
------解决方案--------------------
计算出1到1000的平方和然后在遍历数组的时候减去每个数的平方剩下的就是这2个数的平方和。
得到他们的和和平方和后解方程就得到了
------解决方案--------------------
------解决方案--------------------
这个可以用数学公式来实现.
假设少了的数分别是i, j. 则有:
(式1) 1 + 2 + 3 + ... + n - i - j = 对所有数求和 (1到n的连续数列之和可以求吧)
(式2) 1^2 + 2^2 + 3^2 + ... + n^2 - i^2 - j^2 = 对所有数求平方和 (1到n的连续数列平方和可以求吧)
联立式1和式2, 求解, 可得i, j.
当然你也可以构造其他方程, 例如3次方等等.
------解决方案--------------------
难，，，，，，，，
------解决方案--------------------
贴代码
- Java code
public static void main(String[] args) throws Exception { int[] array = { 1, 3, 2, 7, 5, 6, 4, 9 }; int a = ((1 + 10) * 10) / 2;// 1到1000的和 int b = 10 * (10 + 1) * (2 * 10 + 1) / 6;// 1到1000的平方和 for (int i : array) { a -= i; b -= i * i; } b = (a * a - b) / 2;// 求出2个数的积 System.out.println((a + Math.sqrt(a * a - 4 * b)) / 2 + " " + (a - Math.sqrt(a * a - 4 * b)) / 2); }