面试厦门欧乐时的一道编程题,有兴趣请进！

Question

面试厦门欧乐时的一道编程题，拿出来大家共同学习一下：从1到100000中随意取出两个数，然后将其余99998个数打乱放入数组A中，现在要求遍历一次数组A，就要找到取出的那两个数。要求：最多只能定义5个变量，不能定义数组。大家有兴趣的试试。

Answer 1

一看到题，我首先想到的是利用已知的
1-100000的和-数组A中所有数的和=未知数X+Y的和
1-100000的积/数组A中所有数的积=未知数X*Y的积
然后很容易能解出来
但回头一想，1-100000的积应该是一个很大的数，这方法...
咳

Answer 2

数组A显然是已经生成好，让你用的
就是给你一个数组A里头有被打乱的99998个数
让你找出数组A中少了1-100000中的哪两个数

Answer 3

int count = 1;
Set s1 = new HashSet();
Set s2 = new HashSet();
list l = new ArrayList();while(s1.size()<3)
{
  s1.add(Math.random()*100000);
}for (int i = 0;i<100000;i++)
{
  if(!s1.contains(i))
    s2.add(i);
}如果jdk1.5以上版本，可以直接foreach遍历
for(int j : s2)
{
   if(s1.contains(j))
     l.add(j);
}
没有验证，临时写的。多多指教。呵呵

Answer 4

Random ran=new Random();
int ranA=ran.nextInt(10000);
int ranB=ran.nextInt(10000);
String A[]=new String[10000];
for(int i=0;i<A.length;i++){
if(i!=ranA && i!=ranB){
A[i]=Integer.toString(i);
}else{
System.out.println("取出的数字是"+i);
}
}

是这个意思吗？我不清楚不能定义数组是什么意思，诶。

Answer 5

这个方法是可以的
只是你不用计算出整个1-100000的积
我们只要知道x*y的积就好了
double t = 1;
for(int i = 0; i < 99998; i++)
{
t *= i/A[i]
}
所以x*y = 100000 * t * 99999

Answer 6

晕，看错题了。给出数组A的话：Set s = new HashSet();
list l = new ArrayList();for (int i = 0;i <100000;i++) 
{ 
    s.add(i); 
}for(int j : s) 
{ 
  for(int k=0;k<A.lenght();k++)
  {
    if(j!=A[k])
     l.add(j);
  }
}

Answer 7

double t = 1; //积
double n = 0; //和
for(int i = 0; i < 99998; i++)
{
t *= i/A[i];
n += A[i];
}
t *= (100000*99999);
n = 50000*100001 - n;
解方程组
x + y = n
x * y = t
遍历数组一次
变量个数也满足

Answer 8

在11楼基础上更正下         double t = 1; // 积
double n = 0; // 和
for (int i = 0; i < A.length; i++) {
t = t * (i + 1) / A[i];
n += A[i];
}
t *= (100000 * 99999);
n = 50000 * 100001 - n; // 解方程组
// x + y = n
// x * y = t
// 遍历数组一次
// 变量个数也满足

Answer 9

写一个int数0，然后读那10000个数，读到了谁，就把那个int数相应的位置1，最后看那个int数哪两位是0，就是那两个数。

Answer 10

这题实现起来很难1-10000的阶乘值太大了。
而这种做法的原理是？
i/A[i]
只会弄出0来

Answer 11

估计还是得用hash这类空间换时间的东西吧..说个可能很蠢但理论上可行的办法...用和数组长度相同位数的2进制数来表示每个数字..比如是1-5的话:
1=00001
2=00010
3=00100
4=01000
5=10000
求二进制和是11111
然后假如取了1和3
那就是
2=00010
4=01000
5=10000
求二进制和是11010可以知道少了00100和00001也就是上面的1,3

Answer 12

public static void check(){
int[] a = new int[10];
a[0] = 5;
a[1] = 2;
a[2] = 7;
a[3] = 4;
a[4] = 3;
a[5] = 6;
a[6] = 10;
a[7] = 9;
a[8] = 0;
a[9] = 0;

int index = 8;
for(int i = 0; i<a.length; i++){
while( a[i] != i+1){
if(a[i]== 0){
index = i;
System.out.print("!"+(index+1));
break;
}else{
int temp = a[a[i]-1];
a[a[i]-1] = a[i];
a[i] = temp;
}
}
}
// for(int i:a){
// System.out.print(":"+i);
// }
}输出:
!1!8我写的,还有点小瑕疵,再让我想想~

Answer 13

Arrays.sort(a);
for (int i = 1; i < 100001; i++) {
if (a[i - 1] != i) {
System.out.println("被拿出的数为：" + i);
} }

  

Answer 14

/**
面试厦门欧乐时的一道编程题，拿出来大家共同学习一下：从1到100000中随意取出两个数，然后将其余99998个数打乱放入数组A中，现在要求遍历一次数组A，就要找到取出的那两个数。要求：最多只能定义5个变量，不能定义数组。大家有兴趣的试试。
我假设这两个数为99999，100000
*/
public class SearchTwo{
   public static void main(String args[]){
        long[] A = new long[99998];
        for(int i=0;i<99998;i++){
          A[i]=i+1;
          if(i>99990){
             System.out.println("i="+i);
             System.out.println("A[i]="+A[i]);
         }
        }
        long t = 1; // 积
        long n = 0; // 和
        for (int i = 0; i < A.length; i++) {
            t = t * (i + 1) / A[i];
            n += A[i];
        }
        System.out.println("积:"+t);
        System.out.println("和:"+n);
        t = t*100000*99999;
        //long k=50000;
        //long m=100001;
        //System.out.println("积--------------:"+k*m);
        n = (long)50000*100001-n;
        
        System.out.println("积:"+t);
        System.out.println("和:"+n);
        long x = (long)(Math.sqrt(n*n-4*t)-n)/(-2);
        System.out.println("x="+x);
        System.out.println("y="+(n-x));
        // 解方程组
        // x + y = n
        // x * y = t
        // 遍历数组一次
        // 变量个数也满足
        }
}

Answer 15

给那个数组a能不能存在hashset中 如果能的话 直接循环100000 次输出不包含的   随便提议,有可能不正确,学习中

Answer 16

package com.trust.catchnum;public class CatchNum {

public static void check(){
//数组A[],数组A[]的特点,有length-2项顺序混乱,但是最后两个必须有两个数组单元存放-1,表示缺少的数
int[] a = new int[10];
a[0] = 6;
a[1] = 7;
a[2] = 8;
a[3] = -1;
a[4] = -1;
a[5] = 3;
a[6] = 1;
a[7] = 4;
a[8] = 9;
a[9] = 2;
//两个数
int num1 = -1;
int num2 = -1;
//计数器,记录-1值交换的次数
int count = 0;
//数组有个特点,就是排完序的数组,数组单元中的值减一为数组单元的索引,只要排序,
//然后记录下最后数组单元值为-1的数组单元索引,再加一就是缺少的数的值
for(int i = 0; i<a.length; i++){//开始遍历数组
while( a[i] != i+1){//如果索引值i加一不等于数组单元中的值
if(a[i]== -1){//当数组单元中的值为-1时进入计算
count++;//计数器加一
// System.out.println("!" + i);
//最后两次交换所得到的索引值加一为所要求的两个数
if(count%2 == 1){//奇数次交换,将索引值+1存入num1,最后一次存放的为两个数中之一的一个数
num1 = i + 1;
}
if(count%2 == 0){//偶数次交换,将索引值+1存入num1,最后一次存放的为两个数中之一的一个数
num2 = i + 1;
}
break;//跳出循环,进入下一个数组单元
}else{
//数组单元的交换,将数组单元中的值放入数组索引为其值减一的数组单元
int temp = a[a[i]-1];
a[a[i]-1] = a[i];
a[i] = temp;
}
}
}
//输出这两个数
System.out.println("first num: " + num1);
System.out.println("second num:" + num2);
//输出排序后数组
for(int i:a){
System.out.print(":"+i);
}
}

/**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
check(); }}
搞定啦~大家帮忙看下啊~高手指点下啊~

Answer 17

随你怎么打乱，我用 Arrays.sort 不就行啦！

Answer 18

其实一直在思考 arraylist是不是数组。

Answer 19

在24楼的基础上写了下 还可以改很多哈 只是实现了！
public static void test(){
 int[] a=new int[100000];
 Random random=new Random();
 int v=random.nextInt(100000);
 int s=random.nextInt(100000);
 System.out.println("随机数是："+v+"和"+s);
 for (int i = 0; i < a.length; i++) {
 if (i==v||i==s) {
 continue;
 }
 a[i]=i;
 }
 for (int i = 1; i < 100000; i++) {
if (a[i]!=i) {
System.out.println("拿出的是"+i);
}
}
 }

Answer 20

public static int[] test(int[] a) {
int[] missed = new int[2];
Set set = new HashSet(); for (int index = 0; index < a.length; index++)
set.add(a[index]); int index = 10000, i = 0; Iterator iter = set.iterator(); while (iter.hasNext()) { if (index!=Integer.parseInt(iter.next().toString())) {
missed[i] = index;
i++;
    index--;
}
index--;
}
return missed;
}试试这个，原理是采用hashset的自动排序功能，得到的set里面所有的数字是从大到小排列的，然后用查看究竟少了那个数字返回到数组missed中， 大家不用构造数组A，因为A是已知的。

Answer 21

引用 24 楼 zhaitao81 的回复:
Arrays.sort(a); 
for (int i = 1; i  < 100001; i++) { 
if (a[i - 1] != i) { 
System.out.println("被拿出的数为：" + i); 
} } 
 
想法不错！！！
----------------------------------------------------------------------------------------------
楼上的想法是不可行的，在遇到第一个被拿出的数后，它后面的排序都是不同的，如假设两个数是100和105,在第一个a[100-1]=101时，可以知道拿出的是100,但执行下去，a[101-1]也是不等于101的，实际经过排序已经是102了，这样也会被输出，但101被拿出的结果是错误的，接下来的数据会全部被输出，所以这个算法是行不通的~~

Answer 22

Arrays.sort(a);   人家说了 遍历一次数组A  

Answer 23

可以这么考虑，获得x+y和x*x+y*y的值，那么就可以算出x和y出来。
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <iostream>
#define MAX 100000
void show(int *array,int len)
{
std::cout<<array[len-2]<<'\t'<<array[len-1]<<'\n';
return;
for(int i=0;i<len;++i)
{
if(i%10==0)
std::cout<<std::endl;
std::cout<<array[i]<<'\t';
}
std::cout<<'\n';
}
int run(int *array,int len)
{
unsigned long expectSum=(1+len+2)*(len+2)/2;
unsigned long expectDSum=(len+1)*(len+1)+(len+2)*(len+2);
unsigned long arraySum=0;
unsigned long arrayDSum=0;
for(int i=0;i<len;++i)
{
expectDSum+=(i+1)*(i+1);

arraySum+=array[i];
arrayDSum+=array[i]*array[i];
}
std::cout<<"expectSum:"<<expectSum<<'\t'
<<"expectDSum:"<<expectDSum<<'\t'
<<"arraySum:"<<arraySum<<'\t'
<<"arrayDSum:"<<arrayDSum<<'\n';

unsigned long A=expectDSum-arrayDSum;
unsigned long B=expectSum-arraySum;
unsigned long C=(2*A-B*B);
std::cout<<"x+y="<<B<<'\t'
<<"x*x+y*y:"<<A<<'\n'
<<"2*A-B*B:"<<C<<'\n';
unsigned long x_y=sqrt(C);
std::cout<<"x-y:"<<x_y<<'\n';
std::cout<<"x:"<<(x_y+B)/2<<'\n';
std::cout<<"y:"<<(B-x_y)/2<<'\n';
return 0;
}
int main()
{
int array[MAX];
for(int i=0;i<MAX;++i)
array[i]=i+1;

show(array,MAX);

srand(time(NULL));
for(int i=0;i<MAX;++i)
{
int start=rand()%MAX;
int temp=array[i];
array[i]=array[start];
array[start]=temp;
}
show(array,MAX);

run(array,MAX-2);
return 0;
}

Answer 24

1到100000的和是固定的
然后减去数组里的99998个数字的和，就是x，y的和
1到100000的积是固定的
然后除去数组里的99998个数字的积，就是x，y的积然后解方程 不就出来了

Answer 25

Arrays.sort(a); 
只能遍历一次数组~你这样遍历了n次了~

Answer 26

如果1~100000中比较大的数都排在A[i]的前面的话如：t=1*2*3*...*k/(100000*99999*99999*...*(100000-k)),k>4以上计算机都很难表示这个小数，计算机会当0处理，因此用积的方法行不通

Answer 27

哦，如果是这样，那可以先乘大数
       double t = 1*2; // 积 
        double n = 0; // 和 
        for (int i = 0; i < A.length; i++) { 
            t = t * (100000-i) / A[i]; 
            n += A[i]; 
        } 
       n = 50000 * 100001 - n;         // 解方程组 
        // x + y = n 
        // x * y = t 
      

Answer 28

 想了一段时间了，但还是没什么好的想法，只能看看大家怎么写的，学习下了，，java

Answer 29

死就 死 在 只能 遍历一次 。用 array.sort 吧
毕竟 看不到for 和whlie,,哈 

Answer 30

我现在有有个想法，大家给看一下
假设数组a[10000]
打乱之后，
int temp = 0;
int time = 0;
for(int i =0; i<10000; i++) {
    while(i != a[i]-1) {   //当前位置数组的值与当前的位置不匹配 如：a[0]=1;为匹配。
        time = time +1;
        temp = a[a[i]-1];  
        a[a[i]-1] = a[i];  //把它放在正确的位置。例如：a[0]=7; 则a[6]=7;
        a[i] = temp;       //继续寻找 a[0]=a[6];直到找到a[0]=1结束。
        if(time>9999) {       //没有找到正确的位置。
              System.out.println(i+1);  //输出
        }
    }
    time = 0;
}
不知道，对不对？
找第一个位置的时候最费时了，最坏的情况可能找9次，但是以后的找位置就轻松了，因为他们都是“匹配的”。
效率的话应该很高。
大家给看看！呵呵