日期:2014-05-20  浏览次数:20805 次

求解一笔试题!
昨天参加一个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的为没有的两个数字。
------解决方案--------------------
探讨

引用:
这1.5K-2.5K是薪水吗?太坑爹了吧

高了还是低了?实习工资不敢奢望。

------解决方案--------------------
探讨
先求出2个数的和和乘积然后解方程

------解决方案--------------------
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个数的平方和。

得到他们的和和平方和后解方程就得到了
------解决方案--------------------
探讨

计算出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);
    }