两个比较有趣的面试题(有算法题,不限于Java)

Question

1.既然StringBuffer比String快,为什么jdk中不去掉String,所有的地方都用StringBuffer.2.有100个整数,无序.找出其中第50大的数.(这个不限语言,也不要程序,说下方法就可以了,给出时间复杂度,可以先不考虑有重复数,当然考虑了更好).冒泡冒50次的复杂度是n^2.

Answer 1

第2个用平衡二叉树,时间复杂度只有O(logN)~
已有实现，java中的HashTable~~

Answer 2

楼上的,不是1-100的整数 ,是一百个整数,为什么要取60
排序,这个问题的时间复杂度就是排序的时间复杂度
至于第一个问题,最好是去问sun公司,别人说什么都没用,我想StringBuffer比String快,这应该是一家之言,不足为信,对于定长的字符串,我不认为StringBuffer的效率会高于String

Answer 3

daniel_kaka() 
你说的那个是J2SE？60只是一个比方吧，可以600 6000 60000，至少这样可以缩小范围。就象电视里猜价格一样。在等答案呢

Answer 4

public class Test
{
   int data[];
   public static void main(String args[])\
   {
     for(int i = 0;i <= 100;i++)
      data[i] = (int)(Math.ramdom()*100 +1);
      short(data);
      System.out.println("第50大的数：" + data[50]);
    
    }
  public void short(int data[])
  {
     int show = 0,temp = 0;
     for(int i = 0;show==0&& i<data.length-1;i++)
     {
          show = 1;
          if(data[i] > data[i + 1])
          {
           show = 0
           temp = data[i];
           data[i] = data[i+1];
            data[i+1] = temp;
           }
      }
      
   }
}

Answer 5

1.既然StringBuffer比String快,为什么jdk中不去掉String,所有的地方都用StringBuffer.StringBuffer在很多时候确实比String快, 但Java设计者把String设计成为不可变类, 就是为了使JVM可以对字符串常量进行特殊处理, 比如共享String对象等等. 所以只有在需要经常改变字符串的内容时才使用StringBuffer. 不需要同步的情况下还可采用StringBuilder进一步提高性能...

Answer 6

第2个用平衡二叉树,时间复杂度只有O(logN)~
已有实现，java中的HashTable~~---------------------------------------------
有HashTable这个类吗? 只知道Hashtable, 可它也不是平衡二叉树啊, 八竿子打不到一块儿...哥们说的是TreeSet吧...

Answer 7

1. 请先解释“StringBuffer比String快”。2. 参考quick sort的partition部分。懂C++的话可以参考std::nth_element算法。平均复杂度2n。至于上面用平衡树的朋友，请先列出建立一棵平衡树花费的时间复杂度。

Answer 8

jk88811(你的就是我的，我的还是我的~!) ( ) 信誉：100    Blog   加为好友  2007-04-07 19:46:17  得分: 0  
 
 
   第2个用平衡二叉树,时间复杂度只有O(logN)~
已有实现，java中的HashTable~~---------------------------------------------
有HashTable这个类吗? 只知道Hashtable, 可它也不是平衡二叉树啊, 八竿子打不到一块儿...哥们说的是TreeSet吧...
  
抱歉，说错了，是
TreeMap<Integer,Integer> tm = new TreeMap<Integer,Integer>();
j2se自带的排序表~~ TreeMap

Answer 9

public static void testHashTable(){
        int[] arr = {1,2,3,4,5,6,22,12,45,67,34,56,7,8,9,0};
        TreeMap<Integer,Integer> tm = new TreeMap<Integer,Integer>();
        
        for (int item : arr){
            tm.put(new Integer(item),new Integer(item));
        }
        
        for (Object e : tm.entrySet()){
            System.out.println(((Entry)e).getValue());
        }
    }

Answer 10

to daniel_kaka：
知道TreeMap和TreeSet的区别吗？

Answer 11

iambic() ( ) 信誉：100    Blog   加为好友  2007-4-7 20:23:09  得分: 0  
 
 
   
to daniel_kaka：
知道TreeMap和TreeSet的区别吗？  
 
这点你就不知道可以回去看数据结构了~
map是带key和value的，按照key来排序，key不能重复
set是只有value的，不排重，只有位置概念

Answer 12

1、如果去掉String，那么以前写的java程序都将在新的jre下运行不起来！而且String存在也有
   它自己的意义。2、这是个排序问题，比较快的话，用快速排序算法，具体算法可以查阅有关书籍。

Answer 13

to daniel_kaka：
那请问你为什么用map而不是set？

Answer 14

StringBuffer会覆盖原数据
但是String 不会，这就是为什么它还存在的原因

Answer 15

回答第一个问题：我的个人的想法，要是有错的话请大家指教
首先，StringBuffer在用的时候是要比String ×慢×的。因为String是定死长度的
而StringBuffer是个不定长度的char数组，而且实际占用大小要比存储的字符大，怎么考虑都是要比String 慢的
所谓的StringBuffer 比String快，是在于 在作数据修改的时候
比如：String str＝“dd”；  str＝“dage”； 类似这样的操作是比StringBuffer慢的多
因为String 这个类是 final 的  当你第二次给str赋值的时候，就相当于 str＝new String（“dage”）
这也正是 但一个String 作为参数传递给一个方法的时候
在方法内部修改 String 的值，外面的值是不变的，这跟  int类型当参数效果是一样的
正常来考虑，String 是个类啊，传递的应该是 引用的副本（JAVA是不支持引用传递的）
那为什么 在方法内部改变值，外面的值会不变呢？
其实就是 在你给String在赋一个值的时候
他是 又实例化了一次  相当于从新开辟了一个内存空间
方法里和方法外虽然是一个 String 变量 （String str ＝new String （“dd”）是创建了两个对象，这里说的变量是str）却指向的不同的存储空间。以上是我的理解，有不对的地方请 高手指教啊