一道java面试题

Question

现有1~100共一百个自然数，已随机放入一个有98个元素的数组a[98]。要求写出一个尽量简单的方案，找出没有被放入数组的那2个数，并在屏幕上打印这2个数。注意：程序不用实现自然数随机放入数组的过程。

Answer 1

对a[98]排序
int i = 0;
int count = 0;
for(; i < a.length ; i++) {
    //若i+1 != a[i]，则说明当前附近存在没有放进来的数
         //若i+2 = a[i],则说明当前附近有一个数没放进来，并且这个数是i+2
         count++;
             //如果count == 1，则说明之前已经找到一个，现在直接跳出循环
             break;
         continue;
         //若i+3 = a[i],则说明当前附近有两个数没放进来，并且这两个数是i+2和i+3
         break;
}
这是我的思路！

Answer 2

import java.util.Arrays;
public class Test
{
public static void main(String[] args)
{
int[] arr = {1,3,4,5,7,6,8,9};
int[] finalarr = {0,1,2,3,4,5,6,7,8,9};
Arrays.sort(arr);
int i=0;//控制arr
int j=0;//控制finalarr
while(i<arr.length&&j<finalarr.length){
if(arr[i]!=finalarr[j]){
System.out.println(finalarr[j]);
j++;
}else{
i++;
j++;
}
}
}
}
//output:
//0 
//2

Answer 3

Arrays.sort(arr);把数组排序
int i = 1;
a[i - 1] = i;
如果a里面的值是连续的那第i-1的值就是i
如果不相等，i就是你要要的。

Answer 4

public class Test
{
    public static void main(String[] args)
    {
int[] a = new int[] { 1, 7, 4, 6, 5 };
Map map = new HashMap();
for (int i = 0; i < a.length; i++)
{
    map.put(i, a[i]);
}
for (int i = 1; i < 7; i++)
{
    if (!map.containsValue(i))
    {
System.out.println(i);
    }
}
    }
}不明白效率

Answer 5

int a[] = {2,3,4,5,6,7,8,9};
int[] array = new int[10];
for (int i = 0; i < a.length; i++) {
    array[a[i]-1] = a[i];
}
for (int j = 0; j < array.length; j++) {
    if (0 == array[j]) {
        System.out.println(j+1);
    }
}

Answer 6

09江城地产丽人秀参赛选手 泰驰伊顿阳光：张慧
http://news.wuhan.soufun.com/2009-03-19/2464851.htm
她的博客地址：
http://blog.soufun.com/blog_23226825.htm
请大家务必多多支持，谢谢各位兄弟姐妹！
张龙在这里真心的谢谢大家！
http://newhouse.wuhan.soufun.com/zt/200903/09jclrx.html
点我的相片为我刷刷人气。点点博客也可以刷人气

Answer 7

先排序，大家都说了，然后用a[i] 与i+1判断结果。然后找到一个再用a[i]与i+2　判断。就可以找到了。
如果要更简单的就是，排序，然后打印出来，才100个而以，你看到哪个就是哪个了，再打印出来。

Answer 8

Arrays.sort(array);
for(int i = 0, j = 0; i < 97; i++, j++)
{
   if(array[i] != j + 1)
   {
      System.out.println(j + 1);
      j = j + 1;
   }  
}

Answer 9

int[] b = new int[]{....存入98个随机的1~100的整数}; 
int[] a = new int[100];
for(int t : b)
   a[t-1]=t;
for(int t=0; t < a.length; t++)
   if(a[t]==0)
      System.out.println(t+1);

Answer 10

public class SortTest { public static void main(String[] args) {
int arr[]={1,2,3,4,5,6,9,7};
Integer brr[]=new Integer[11];
for(int i=0;i<arr.length;i++){
brr[arr[i]]=arr[i];
}
for(int j=1;j<11;j++){
if(brr[j]==null)
System.out.println(j);
} }}

Answer 11

public class SortTest { public static void main(String[] args) {
int arr[]={1,2,3,4,5,6,9,7};
Integer brr[]=new Integer[11];
for(int i=0;i<arr.length;i++){
brr[arr[i]]=arr[i];
}
for(int j=1;j<11;j++){
if(brr[j]==null)
System.out.println(j);
} }}

Answer 12

Arrays.sort(array); 
if(array[0]!=1)
    System.out.println(1);
for(int i = 0; i < 97; i++) 
{ 
    if(array[i]+1 != array[i+1]) 
    { 
        System.out.println(array[i]+1); 
    }  
}

Answer 13

刚才没有考虑到连续两个数没放进来的情况，估计也有其他兄弟忽略了这个问题Arrays.sort(array); 
if(array[0]!=1){
    System.out.println(1);
        if(array[1] != 2)
            System.out.println(2);
}
for(int i=0; i<97; i++) { 
    if(array[i] != array[i+1]) { 
        System.out.println(array[i]+1); 
        if(array[i] != i+2)
           System.out.println(i+2); 
    }  
}

Answer 14

import java.util.ArrayList;/**
 * 
 *//**
 * @author 苏帅
 *Mar 27, 20098:43:56 AM
 *
 */
public class Test1 {
@SuppressWarnings("unchecked")
public static void main(String[] args) {

int[] a = new int[98];
ArrayList list = new ArrayList();
for(int i = 1;i <= 100 ; i++){
list.add(i);
}
for(int i = 0;i < a.length ;i++){
int index = 0;
if((index = list.indexOf(a[i])) > -1){
list.remove(index);
}
}
System.out.println(list.get(0));
System.out.println(list.get(1));

}}

Answer 15

import java.util.ArrayList;/**
 * 
 *//**
 * @author 苏帅
 *Mar 27, 20098:43:56 AM
 *
 */
public class Test1 {
@SuppressWarnings("unchecked")
public static void main(String[] args) {

int[] a = new int[98];
ArrayList list = new ArrayList();
ArrayList listTemp = new ArrayList();
for(int i = 1;i <= 100 ; i++){
list.add(i);
}
for(int i = 0;i < a.length ;i++){
listTemp.add(a[i]);
}
list.removeAll(listTemp);
System.out.println(list.get(0));
System.out.println(list.get(1));
}}

Answer 16

不知道list.removeAll(listTemp);的执行效率如何？

Answer 17

package testarray;
public class Random {
public static void main(String[] args) {
int b[] = new int[101]; // 要跳过0这个数
for (int i = 1; i <= 98; ++i) {
b[a[i]] = 1;// 使b[]中以a[i]为下标的数为1，初值为全0
} 
int N =5;
System.out.println("没有放到a[98]中的元素：");
for (int i = 1; i <= 100; ++i) {
if (b[i] == 0) {  //说明这个元素的下标没有在a[]中出现
System.out.println(i);
}
} }}

Answer 18

Arrays.sort(array);
int j = 100;
for(int i = 0; i < 50;i++)
{ 
   if((a[i]+a[j])>100)
   {
      System.out.println(a[i]-1);
   }
   if((a[i]+a[j])<100)
   {
     System.out.println(a[j]+1);
   }
   j = j-i;
}

Answer 19

int[] p = new int[100];
for(int i = 0; i < a.length; i++)
{
   int t = a[i];
   p[t] = a[i];
}
for(int i = 0; i < p.length; i++)
{
   if(p[i] == 0 && i != 0){
      System.out.println(i);
   }
}这个简单不用排序 直接把值对应地址 存数组  最后扫下 如果为空 就相当于 这个值没有存进来

Answer 20

有没有正确答案?基本都是一个思路,先定义个100的数组,然后随机产生数,产生一个就让数组中的那个数为0,最后不为0的两个数就是了!我的代码: public static void main(String[] args) {

      int[] arr1=new int[100];
int[] arr2=new int[98];
int temp;
for(int i=0;i<arr1.length;i++)
{
arr1[i]=i+1;
}
for(int i=0;i<arr2.length;i++){
    do {
temp = (int) (Math.random() * 100 + 1);
} while (arr1[temp-1]==0);
    arr2[i]=temp;
    arr1[temp-1]=0;
}
for(int i=0;i<arr1.length;i++)
{
if(arr1[i]!=0)
System.out.println(arr1[i]);
}

其实意思都是一样的,不过我觉得应该还有更简单的方法,他出这题的本意应该不是这个吧

Answer 21

我认为使用treeMap的效率是最高的，通过键和键值的比较，如果不一样，键就是那个数，直接打印出来，多简单，效率又高！

Answer 22

还有一个最简单的 ！！  
就是把那个a[98] 放到list 里面！  
在创一个 长度100的 list 里面原数 1-100；
最后调用方法 removeAll() 
最后剩下在 长度为100 list 的两个数就是结果了 ！

Answer 23

for(int i=1,i<101;i++){
    for(int j=0;j<98;j++){
        if(i!=a[j]){
            System.out.println(i);
        }
    }
}

Answer 24

for(int i=1,i <=100;i++){ 
    for(int j=1;j <=98;j++){ 
        if(i!=a[j]){ 
            System.out.println(i); 
        } 
    } 
这样写是不是更简单一此呢？？

Answer 25

int[] a = {1,2,3,5,6,7,8,9,10};

int one = 0;
int two = 0;
Arrays.sort(a);   //对数据进行排序 从小到大
for(int i=0; i<a.length; i++){
if(one == 0 &&  a[i] > i+1){  //判断第一个值 判断依据 这个值都必须比数组下界＋1大
one = a[i]-(a[i]-i-1);
}
if(one != 0 && a[i] > i+2){   //判断第二个值 判断依据 因为有了第一个值 所以这个值必须比数组下界＋2大
two = a[i]-(a[i]-i-2);
break;
}
}
if (two == 0){     //如果是最后一个值，则以上二方法不能判断 只能取最后一个值＋1
two = a[a.length-1]+1;
}
System.out.println(one + "," + two);
上面方法应该是最简单的一个方法 一次循环 可以得出结果 
因为没时间去组织 写得有些乱 慢慢看应该会明白
有时间的朋友可以写一个封装来，要再好的效果 可以在现在算法的基础上 加上二分法。
用算法 这题目应该是最好的。

Answer 26

public void find2number(int[]arg)
{
Arrays.sort(arg);
int tmp=1;
    for(int i=0;i<98;i++)
    {
     if(arg[i]!=i+tmp)
     {
     System.out.println("其中一个数是"+(i+tmp));
     tmp++;
     if(tmp==3)
     break;
     }
    }
    if(tmp==1)
     System.out.println("这两个数分别是99和100");
    if(tmp==2)
     System.out.println("其中一个数是100");
    
    
}

Answer 27

不好意思 刚刚粗心大意没发现两个连续数的时候会出现错误,解决方法就是在tmp++后面插入i--就ok了

Answer 28

int[] b = new int[]{....存入98个随机的1~100的整数}; 
Vector a = new Vector();
for(int i=0;i<100;i++){//定义一个Vector，里面顺序放置1到100
  a.add(i+1);  
}
for(int j =0 ;j<98;j++){
   a.remove(b[j]);
} 
 System.out.println("这两个数分别是"+a.elements(0)+"、"+a.elements(1));

Answer 29

int b[]=new int[101];
for(int i=0;i<=100;i++)
{
  b[i]=i;
}
for(int j=0;j<98;j++)
{
  b[a[j]]=0;
}
for(int k=1;k<=100;k++)
{
  if(b[k]==0)
  {
    system.out.println(b[k]);
  }
}
只需要执行3次for循环而已
如果排序，那个时间复杂度可就高了

Answer 30

最近写c写多了留了后遗症
第一个for循环完全可以不要，改成
int b[]=new int[101];
for(int j=0;j <98;j++)
{
  b[a[j]]=a[j];
}
for(int k=1;k <=100;k++)
{
  if(b[k]!=0)
  {
    system.out.println(b[k]);
  }
} 

Answer 31

Arrays.sort时间复杂度是O(n^2),说排序的已经输了.
牺牲空间换取时间复杂度O(n)的解法是正确的.
这题和将1-100排序(时间复杂度O(n))是一样的.