剑指offer-例题第一次只出现一次的字符

题目描述：

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

我的解法：

import java.util.*; public class Solution { public int FirstNotRepeatingChar(String str) { if(str==null||str.length()==0) return -1; ArrayList<ListNode> result=new ArrayList<ListNode>(); for(int i=0;i<str.length();i++) { int j; for(j=0;j<result.size();j++) { if(result.get(j).ch==str.charAt(i)) { result.get(j).num++; break;//这里是个坑，一定要break } } if(j==result.size()) { ListNode k=new ListNode(str.charAt(i),1,i); result.add(k); } } for(int i=0;i<result.size();i++) { if(result.get(i).num==1) return result.get(i).index; } return -1; } } class ListNode{ char ch; int num; int index; public ListNode(char ch,int num,int index){ this.ch=ch; this.num=num; this.index=index; } }

要根据出现的先后顺序，就没办法将字符值转换为数组下标，那样就是按字符值大小排序了，为解决这一问题，方法如下：

public class Solution { public int FirstNotRepeatingChar(String str) { if(str==null||str.length()==0) return -1; int[] result=new int[100]; int[] index=new int[100]; for(int i=0;i<str.length();i++) { if(result[str.charAt(i)-'A']==0) index[str.charAt(i)-'A']=i; result[str.charAt(i)-'A']++; } for(int i=0;i<str.length();i++) { if(result[str.charAt(i)-'A']==1)//这里是个坑，这样才能保证是按出现顺序排列的而不是按字符大小顺序排列的 return index[str.charAt(i)-'A']; } return -1; } }

我的解法存在的问题：

1、时间复杂度为O(n*n)    还有提升的空间

2、为保证按出现顺序而不是按字符大小顺序，第二次应该在str上遍历而不是result上,而且这样还可以直接得到位置值

3、字符转换为数组下标，直接使用result[char]   相当于改变了数组中下标为  char对应ASCII值   的元素值

     这样也不需要在每次判断时都遍历一遍数组，节省时间

4、题目中只涉及到字母，一个字节就已足够，有种情况，因此数组大小设为256，如果任意字符出现的话，char是2字节的数据类型

5、可以直接得到位置值，不需要通过另一个数组存储第一次出现的位置

正确解法：

时间复杂度：O(n)

空间复杂度：O(1)

public class Solution { public int FirstNotRepeatingChar(String str) { if(str==null||str.length()==0) return -1; int[] result=new int[256]; for(int i=0;i<str.length();i++) { result[str.charAt(i)]++; } for(int i=0;i<str.length();i++) { if(result[str.charAt(i)]==1) return i; } return -1; } }

每个字符根据其ASCII码值作为数组下标

 

相关题目：(哈希表的应用)

1、定义一个函数，输入两个字符串，从第一个字符串中删除在第二个字符串中出现过的所有字符。例如从第一个字符串"We are students. "中删除在第二个字符串"aeiou"中出现过的字符得到的结果是"W r Stdnts. "。

时间复杂度：O(n)

空间复杂度：O(1)

public String FirstNotRepeatingChar(String str1,String str2) { if(str1==null||str1.length()==0) return str1; if(str2==null||str2.length()==0) return str1; int[] num=new int[65536]; for(int i=0;i<str2.length();i++) num[str2.charAt(i)]++; StringBuilder s=new StringBuilder(str1); for(int i=0;i<s.length();i++) { if(num[s.charAt(i)]!=0) { s.deleteCharAt(i); i--;//这是一个坑 } } return s.toString(); }

2、定义一个函数，删除字符串中所有重复出现的字符。例如输入"google",删除重复的字符之后的结果是"gole"。

时间复杂度：O(n)

空间复杂度：O(1)

public String FirstNotRepeatingChar(String str1) { if(str1==null|str1.length()==0) return str1; StringBuilder s=new StringBuilder(); int result[]=new int[65536]; for(int i=0;i<str1.length();i++) { if(result[str1.charAt(i)]==0) { result[str1.charAt(i)]++; s.append(str1.charAt(i)); } } return s.toString(); }

下面是错误解法 ：

s发生变化不利于此问题解决

public String FirstNotRepeatingChar(String str1) { if(str1==null|str1.length()==0) return str1; StringBuilder s=new StringBuilder(str1); int result[][]=new int[65536][2]; for(int i=0;i<str1.length();i++) { if(result[str1.charAt(i)][0]==0) { result[str1.charAt(i)][1]=i; } result[str1.charAt(i)][0]++; } //这是一个坑，以下要全部在s上进行 for(int i=0;i<s.length();i++) { if(result[s.charAt(i)][0]>1) { if(i!=result[s.charAt(i)][1]) { s.deleteCharAt(i); i--;//这是一个坑，删除了长度发生变化，i也要跟着变化 但是i都已经发生变化了就不能判断它是否是第一次出现了 } } } return s.toString(); }

3、在英语中，如果两个单词中出现的字母相同，并且每个字母出现的次数也相同，那么这两个单词互为变位词。例如silent与listen、evil与live等互为变位词。请完成一个函数，判断输入的两个字符串是不是互为变位词。

时间复杂度：O(n)

空间复杂度：O(1)

public static boolean FirstNotRepeatingChar(String str1,String str2) { int[] s1=new int[65537]; int[] s2=new int[65537]; for(int i=0;i<str1.length();i++) s1[str1.charAt(i)]++; for(int i=0;i<str2.length();i++) s2[str2.charAt(i)]++; for(int i=0;i<str1.length();i++) { if(s1[str1.charAt(i)]!=s2[str1.charAt(i)]) return false; } for(int i=0;i<str2.length();i++) { if(s2[str2.charAt(i)]!=s1[str2.charAt(i)]) return false; } return true; }