一道笔试题(java)

Question

求第一个无重复字符,如"total"的第一个无重复字符是o,"teeter"的第一个无重复字符是r,效率要优于O(n的平方)
public static Character FirstNonRepeated(String)

Answer 1

public static char FirstNonRepeated(String str){
char[] array = str.toCharArray();
int num = 0;
for(int i=0 ; i<array.length ; i++){
for(int j=i+1 ; j<array.length ; j++){
if(array[i] == array[j]){
num++;
}
}
if(num == 0){
return array[i];
}else{
num = 0;
}
}
return 0;
}

Answer 2

都是ascii字符的话比较简单，O(n)就可以了
public static Character FirstNonRepeated(String string) {
int[] counter = new int[128];
for (int i = 0; i < string.length(); i++) {
char ch = string.charAt(i);
counter[ch]++;;
}
for (int i = 0; i < string.length(); i++) {
char ch = string.charAt(i);
if(counter[ch] == 1)
return ch;
}
return null;
}

Answer 3

用时：20分钟import java.util.LinkedList;
import java.util.List;
public class FirstNotDuplicate { public static void main(String[] args){

findNoneDup("total");
findNoneDup("Bee");
findNoneDup("example Complex");
findNoneDup("BeeB");

}

private static Character findNoneDup(String str){
LinkedList<Character> charList=new LinkedList<Character>();
//第一步，先将str拆成字符list
for(int i=0; i<str.length();i++){
charList.add(str.charAt(i));
}

//第二步，遍历，每次遍历都从list中移除相同的字符，如果移除字符数>1说明有重复
//双重循环，满足 O(n^2)
boolean find=false;
Character result=null;
while(charList.size()>0 && !find){
char c=charList.getFirst();
int removeCount=0;
for(int i=charList.size()-1;i>=0;i--){
if(charList.get(i).equals(c)){
charList.remove(i);
removeCount++;
}
}
if (removeCount==1){
find=true;
result=c;
}
}
if (find){
System.out.println(str+" 中，第一个不重复字符为：\t"+result);

}else{
System.out.println(str+" 中，不存在不重复字符为。");
}
return result;
}
}

Answer 4

char ch = string.charAt(i);
            counter[ch]++;;
这个ch是 char型的，counter是int[]的，能这么写吗，counter[ch]++;不会报错吗

Answer 5

java技术群:69705156
可以交流

Answer 6

public static char FirstNonRepeated(String s){
         char[] w = s.toCharArray();
         for(int i=0;i <s.Length;i++) 
         { 
                if (w.Length-s.Replace(w[i].ToString(),"").Length==1) 
                { 
                    System.out.println(w[i].ToString()); 
                    break; 
                } 
                
            }             }
这是别人的写的，感觉思路不错，
效率也差不多吧 

Answer 7

考虑了一下3楼的
然后自己写了一个,经过测试效率高于3楼public static Character aaa(String string){
int[] a = new int[string.length()];
int num=0;
for(int i=0;i<string.length();i++){
a[i] = string.indexOf(string.charAt(i));
//System.out.println(a[i]);
}
for(int j=0;j<a.length;j++){
num=0;
for(int i=0;i<a.length;i++){
if(a[j]!=a[i]){
num++;
}

}
if(num==a.length-1){
return string.charAt(a[j]);
}
}
return '?';
}

Answer 8

支持汉字，思路和3楼的差不多
但用的是字符对应的 hashCode import java.util.Date;
import java.util.Enumeration;public class Other {
public static void main(String[] args) {
long begin = new Date().getTime();
String str = "求第一个无重复字符,如\"total\"的第一个无重复字符是o,\"teeter\"的第一个无重复字符是r,效率要优于O(n的平方) public static Character FirstNonRepeated(String)";
Hashtable htNumber = new Hashtable();// 以字符的 hashCode 为 key，int[2] 为 value
int order = 0;
int length = str.length();
for (int i = 0; i < length; i++) {
Character c = new Character(str.charAt(i));
if(htNumber.containsKey("" + c.hashCode())){
// crtArray[0]存放出现次数，crtArray[1]存放出现顺序
int[] crtArray = (int[])htNumber.get("" + c.hashCode());
crtArray[0] = crtArray[0] + 1;// 次数加1
htNumber.put("" + c.hashCode(), crtArray);
}else{
order++;
// 第一次出现该字符时，次数为1，顺序加1后保存
htNumber.put("" + c.hashCode(), new int[]{1, order});
}
}

order = length;
char first = 0;
Enumeration em = htNumber.keys();
while(em.hasMoreElements()){
String key = em.nextElement().toString();
int[] crtArray = (int[])htNumber.get(key);
// 顺序最小，且次数为1
if(order > crtArray[1] && crtArray[0] == 1){
order = crtArray[1];
first = (char)Integer.parseInt(key);
}
}

System.out.println(first);
System.out.println("消耗时间：" + (new Date().getTime() - begin) / 1000.0 + "毫秒");
}
}

Answer 9

都说三楼的好，我就是看不懂，没法给分，
char ch = string.charAt(i); 
            counter[ch]++;; 
这个ch是 char型的，counter是int[]的，能这么写吗，counter[ch]++;不会报错吗 
[]里不应该是数字吗，他里边写个ch是什么意思啊，

Answer 10

1、counter[ch] 里会将 ch 自动转换为 int 类型
2、counter[ch]++ 运行了一下，不会报错。估计是因为这个数组是基础类型数组 int[]

Answer 11

public static Character FirstNonRepeated(String str){
    for(int i=0; i<str.length(); i++) {
        char c = str.charAt(i);
        if(str.indexOf(c) == str.lastIndexOf(c)){
             return c;
        }
    }
    return '0';
}

Answer 12

不知道indexOf是否把时间复杂度加到了O(n^2)了

Answer 13

public static char getChar(String text){   
        char c =0xff;   
        for(int index =0;index <text.length();index ++){   
            c =text.charAt(index);   
            if(text.indexOf(c) ==text.lastIndexOf(c))
             break;   
        }   
         return c;   
        }   

Answer 14

 return ch,这行报错,和我的jdk版本有关系吗?我是1.4
还有能简单说下 counter[ch]++;这个的原理吗?是从int 数组的第0位依次放入的吗?

Answer 15

厉害，确实不错，jdk1.4可能会报错吧

Answer 16

这个不错，简单明了
public static char getChar(String text){  
        char c =0xff;  
        for(int index =0;index <text.length();index ++){  
            c =text.charAt(index);  
            if(text.indexOf(c) ==text.lastIndexOf(c)) 
            break;  
        }  
        return c;  
        }  

Answer 17

import static  java.lang.System.out;
public class DumpChar
{
public static void main(String[] args)
{
String str = "teeter";
out.println(firstNonRepeated(str));
}
public static Character firstNonRepeated(String str)
{
int[] counts = new int[52];
for(int i = 0 ; i < 52 ; i++)
{
counts[i] = 0;
}
for(int i = 0 ; i < str.length() ; i++)
{
char cur = str.charAt(i);
int index =  cur > 'z'? cur - 'A' + 26:cur - 'a';
counts[index]++;
}
for(int i = 0 ; i < str.length() ; i++)
{
char cur = str.charAt(i);
int index =  cur > 'z'? cur - 'A' + 26:cur - 'a';
if(counts[index] == 1)
{
return cur;
}
}
return null;
}
}o(n)

Answer 18

不是说效率要优于o(n的平方)吗
有好几个是o(n的平方)的

Answer 19

public static Character GetFirstChar(String string) 
{
        int[] nChar = new int[128];
        
        char a[] = string.toCharArray();
        
        for (int i = 0; i < a.length; i++) 
        {
         nChar[a[i]]++;
        }
        for (int i = 0; i < a.length; i++) 
        {
            
            if(nChar[a[i]] == 1)
            {
             return a[i];
            }
        }
        
        return null;
    }

Answer 20

帮楼主解释一下三楼的思路！   “counter[ch]”，由于这里的ch是单个字符，作为数组下标时，会被自动转化为对应的ASCII值（也就是int类型的整数）   楼主的思路是让string中的每个字符对应的ASCII值作为counter的下标，先不管string字符是否重复，让任何字符'x'对应的counter[x]都会被加1.比如"cbcbac",那么counter['c']=3,counter['b']=2,counter['a']=1; 这样就能确定‘a’是我们想要的。  代码如下：
public class SearchSingleChar {
 static int[] counter = new int[128];
 static public char FirstNonRepeated(String string){
int[] counter = new int[128];
        for (int i = 0; i < string.length(); i++) {
            char ch = string.charAt(i);
            counter[ch]++;;
        }
        System.out.println("包含字符'c'的个数为："+counter['c']);
        System.out.println("包含字符'b'的个数为："+counter['b']);
        System.out.println("包含字符'a'的个数为："+counter['a']);
        for (int i = 0; i < string.length(); i++) {
            char ch = string.charAt(i);
            if(counter[ch] == 1)
                return ch;
        }
        return 0;
    }
public static void main(String args[]){
SearchSingleChar ssc=new SearchSingleChar();
String string="cbcbac" ;
char myChar=ssc.FirstNonRepeated(string);
        System.out.println("该string中仅包含的一个的字符为："+myChar);
       
}

}
注意“   System.out.println("包含字符'c'的个数为："+counter['c']);
        System.out.println("包含字符'b'的个数为："+counter['b']);
        System.out.println("包含字符'a'的个数为："+counter['a']);”能帮助楼主理解。

Answer 21

public class AA { public static void main(String[] args) {
String str = "total";
String sub = "";
for (int i = 0; i < str.length(); i++) {
sub = str.substring(i,i+1);
if(str.indexOf(sub) == str.lastIndexOf(sub)) {
System.out.print(sub + " 是第一个无重复字符!");
break;
}
}
}
}

Answer 22

public void FirstNonRepeated(String str) {
String sub = "";
for (int i = 0; i < str.length(); i++) {
sub = str.substring(i,i+1);
if(str.indexOf(sub) == str.lastIndexOf(sub)) {
System.out.print(sub + " 是第一个无重复字符!");
break;
}
}
}

Answer 23

public static Character FirstNonRepeated(String value)
{
   boolean isExit = false;
   String temp = "";
   Character cr = null;

   while(!isExit)
   {
if(null != value && value.length() > 0)
{
   char c = value.charAt(0);
   value = value.substring(1,value.length());
           if(value.indexOf(c) == -1 && temp.indexOf(c) == -1)
   {
       isExit = true;
       cr = c;
   }

       temp = temp + c;
}
else
{
      isExit = true;
}

    }


    return cr;
}
这个是我写的，上面有些朋友的代码应该没有考虑到效率的问题，题目中要求优先级高于N的平方，我这个方法最多执行N，效率应该还可以的，请多多指教！
（其中的N指的是字符串的长度！）

Answer 24

public static Character FirstNonRepeated(String value)
{
boolean isExit = false;
String temp = "";
Character cr = null;
int i = 0;

while(!isExit)
{
i++;
if(null != value && value.length() > 0)
{
char c = value.charAt(0);
value = value.substring(1,value.length());
if(value.indexOf(c) == -1 && temp.indexOf(c) == -1)
{
isExit = true;
cr = c;
}

temp = temp + c;
}
else
{
isExit = true;
}

}

System.out.println(i);

return cr;
}这个是我写的，可以测试一下我的效率，应该比前面这些答案效率高很多，做多执行N次！

Answer 25

请问为什么要把int数组长度设为128，ASCII不是低七位有效的吗？把长度定位255吧。

Answer 26

3楼的有错误，就是   "counter[ch]++;" 这句，类型不对，counter[]是int型，而ch是char型的，
支持9楼。 

Answer 27

62楼的貌似循环最多执行N次
但是在执行下面这段处理时
    if(value.indexOf(c) == -1 && temp.indexOf(c) == -1)
    {
        isExit = true;
        cr = c;
    }
每次都相当于遍历了整个字符串（也可以说成对应的char[]）。
楼主所说的时间复杂度O(n)中的n应该说的是字符串的长度..
而不是循环的次数。

Answer 28

恩，String.indexOf(String)这个方法也是遍历整个字符串，这点没考虑进来，呵呵！毕竟新手，谢谢指正！

Answer 29

System.out.println("请输入：");
Scanner sc=new Scanner(System.in);
String s=sc.next();char[] ch=s.toCharArray();
for(int i=0;i<ch.length;i++){
for(int j=0;j<ch.length;j++){
if(ch[i]==ch[j]&&i!=j) break;
else if(j==ch.length-1){
System.out.println(ch[i]);
}

}

}

Answer 30

第二个for循环应该可以改一下
for(int j=0;j<a.length;j++){
            num=0;
            for(int i=j;i<a.length;i++){
                if(a[j]!=a[i]){
                    num++;
                }
                
            }
            if(num==a.length-1-j){
                return string.charAt(a[j]);
            }
        }

Answer 31

for (int i = 0; i < string.length(); i++) {
            char ch = string.charAt(i);
   if(string.indexOf(ch)==string.lastIndexOf(ch)){
          System.out.println(ch);
          break();
}
        }

Answer 32

3楼的如果只是字母串，字母的ascii码是从65开始到90，90到122所以数组定为128的大小了这程序很c++啊哈哈18楼的
public static char FirstNonRepeated(String s){ char[] w = s.toCharArray(); for(int i=0;i <s.Length;i++) { if (w.Length-s.Replace(w[i].ToString(),"").Length==1) { System.out.println(w[i].ToString()); break; } } }
这才是真正的java程序啊哈哈不过效率很难控制了，谁知道那些方法又是什么复杂度等级的其他的程序都没这俩好

Answer 33

这个效率明显低于3楼啊，indexOf查找字符串的时候是要遍历整个字符串的，放到for循环里，效率是（n^2），理论上已经没有比3楼效率在高的算法了。

Answer 34

我也贴一个。不过是用递归方法：
public class Other {
static String name ="teeter";
public static void main(String[] args) { 
getResult(String.valueOf(name.charAt(0)), 0);
} 

public static void getResult(String str,int i){
int count=0; 
int m=name.indexOf(str); 
while(m!=-1){ 
m=name.indexOf(str,m+1); 
count++;
} 
if(count<2){
System.out.println(str);
}else if(i<name.length()-1){
getResult(String.valueOf(name.charAt(i+1)), i+1);
}
}
}

Answer 35

当然了 indexof 方法 没有string.charAt() 效率高。
 但循环次数绝对减少了。

Answer 36

在说一句，出现indexof，replace的算法在这道题面前应该没有什么价值了
如果不考虑空间，用数组的速度应该可以pk倒哈希。唉，有待斟酌，回家研究。

Answer 37

public static Character FirstNonRepeated2(String str){

char c[] = str.toCharArray();
for(int i=0;i<c.length;i++){
int count=0;
char temp = c[i];
for(int j=0;j<c.length;j++){
if(temp==c[j]){
count++;
}
}
if(count==1){
return temp;
}
}
return '0';
}