在一个字符串中找到第一个只出现一次的字符(java实现)

时间:2021-05-28 11:13:09

昨天笔试的时候碰到的算法题大致有两类:字符串处理类、链表,面前数据结构还没开始复习,故重点思考了字符串处理类的题,结果写的还是乱七八糟。在网上搜索之后,总结一下看到的算法


最新查到是的下面的算法:

 1     public class s17 {  
 2         public static char firstOne(String s)  
 3         {  
 4             char result = '0';  
 5             char temp;  
 6             int[] num = new int[52];  
 7             for (int i = 0; i < s.length(); i ++)  
 8             {  
 9                 temp = s.charAt(i);  
10                 if ( temp >= 'a' && temp <= 'z' )  
11                 {  
12                     num[temp - 'a']++;  
13                 }  
14                 else  
15                     if (temp >= 'A' && temp <= 'Z')  
16                     {  
17                         num[temp - 'A' + 26] ++;  
18                     }  
19             }  
20             for (int i = 0; i < num.length; i ++)  
21             {  
22                 if (num[i] == 1)  
23                 {  
24                     if (i >= 0 && i <=26)  
25                     {  
26                         result = (char)(i + 'a');  
27                     }  
28                     else  
29                         result = (char)(i - 26 + 'A');  
30                     break;  
31                 }  
32             }  
33             return result;  
34         }  
35         /** 
36          * @param args 
37          */  
38         public static void main(String[] args) {  
39             // TODO Auto-generated method stub  
40     //      String s = "xabb";  
41             String s = "abaccdeff";  
42     //        
43             char c = firstOne(s);  
44             System.out.println(c);  
45         }  
46     }  

后来证明此算法不正确,首先,字符限定在了字母;其次,因为已经根据ASCII码进行了排序,所以如:xabb,输出的结果却是a,而不是x(转载)。

查到的以下算法才是正确的(由于字符(char)是一个长度为8的数据类型,因此总共有可能256 种可能):

 1     public static char FirstNotRepeatingChar(String str) {  
 2         
 3         if (str == null||str.length()<1){  
 4             return 0;  
 5         }  
 6         char[] strArr=str.toCharArray();//将字符串变为字符数组
 7         int[] charArr = new int[256];  
 8         for (int i = 0; i < strArr.length; i++) {  
 9             System.out.println(strArr[i]);
10             System.out.println(Integer.valueOf(strArr[i]));
11             charArr[strArr[i]]++;
12             System.out.println(charArr[strArr[i]]);
13         }  
14         for (int i = 0; i < strArr.length; i++) {  
15             if (charArr[strArr[i]] == 1){  
16                 return strArr[i];  
17             }  
18         }  
19         return 0;  
20     }

有同学还提出可以用map实现减少时间复杂度,这个还没想明白,待补充。。