剑指offer----第一个只出现一次的字符位置----java实现

心已赠人 2022-09-23 08:27 78阅读 0赞

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符的位置。若为空串，返回\-1。位置索引从0开始。

如果从头开始让每一个字符都与其后面的字符相比较，当第一个出现一次的字符，就结束程序。但是这种算法的时间复杂度是O(n^2);

思路：我们可以遍历统计每个字符在字符串中出现的次数，把它保存在数组中，可以利用哈希算法，让字符的ASCII码与数组的键值保持一定的关系，数组的值用来保存次数，这样就形成key-value对，根据字符的ASCII值就可以找到它它在数组中保存它出现的次数的位置。

题目中是全部由字母组成，大写字母的ASCII码在65-90，小写字母在97-122之间，一共有52个字母。

（1）创建一个数组大小为52的数组，来保存每个字母出现的次数；

（2）ASCII码值与数组索引之间的关系，

A（ASCII码65）保存在数组中0位置，即大写字母的ASCII码（设为m）与其在数组中的位置之间的关系：m-65

a(ASCII码97)保存在数组中26位置，即小写写字母的ASCII码（设为n）与其在数组中的位置之间的关系：n-71

（3）第一次遍历字符串，更新字母出现次数，每扫描到一个字符就在其数组中对应的位置将其次数\+1；

（4）第二次遍历字符串，查找字母出现次数，每扫描到一个字符就查找器在数组中对应位置的值是否为1，找到第一个，将数组索引大小返回并退出程序。

public int FirstNotRepeatingChar(String str)
    	{
    		int index = -1;//如果字符串为空返回-1
    		if(str != null )
    		{
    			char [] charArray = str.toCharArray();//将字符串转换成字符数组
    			int[] count = new int[52];//创建一个int型长度为52的数组，用来保存每个字母出现的次数
    			
    			//第一次遍历字符串，更新字母出现次数（根据字母找到数组的位置将值+1）
    			for (int i = 0; i < charArray.length; i++)
    			{
    				//如果字母在65-90之间，在数组中的位置为ASCII-65，并将次数+1
    				if(charArray[i]>=65 && charArray[i]<=90)
    				{
    					count[charArray[i] - 65]++;
    				}
    				//如果字母在97-112之间，在数组中的位置为ASCII-71，并将次数+1
    				if(charArray[i]>=97 && charArray[i]<=112)
    				{
    					count[charArray[i] - 71]++;
    				}
    			}
    			
    			//第二次遍历字符串，查找字母出现次数（根据字母找到次数保存在count数组中的位置得到出现的次数）
    			for (int i = 0; i < charArray.length; i++)
    			{
    				//如果字母在65-90之间，在数组中的位置为ASCII-65，并将次数+1
    				if(charArray[i]>=65 && charArray[i]<=90)
    				{
    					if(count[charArray[i] - 65] == 1)
    						{
    						  index = i;
    						  break;
    						}
    				}
    				//如果字母在97-112之间，在数组中的位置为ASCII-71，并将次数+1
    				if(charArray[i]>=97 && charArray[i]<=112)
    				{
    					if(count[charArray[i] - 71] == 1)
    						{
    						  index = i;
    						   break;
    					    }
    				}
    				
    		    }
    			
    		}
    		return index;
    	}