剑指offer_字符流中第一个只出现一次的字符

阳光穿透心脏的1/2处 2022-06-09 06:57 327阅读 0赞

/*
    请实现一个函数用来找出字符流中第一个只出现一次的字符。
    例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。
    当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
    如果当前字符流没有存在出现一次的字符，返回#字符。
    
    如何理解字符流？与以前做过的
    int firstNotRepeatingChar(String str) 在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置
    有什么区别？
    以前的题目可以对str进行操作，现在不存在这么一个str，
    按照以前的做法，可以做到知道哪些字符出现一次，但不能确定哪个是第一个
    
    剑指offer思路：用一个量记录字符出现的前后顺序
    */
    
    class  FirstAppearingOnce
    {
    	int[] countOfChar=new int[256];
    	//Insert one char from stringstream
    	int index=1;
        public void Insert(char ch)
        {
    		if (countOfChar[ch]==0)
    		{
    			countOfChar[ch]=index++;//之前没有出现过的字符，则将index放入对应位置，记录出现顺序
    		}else
    			countOfChar[ch]=-1;//之前已经出现过，标记为-1
        }
    
    	//return the first appearence once char in current stringstream
        public char firstAppearingOnce()
        {	
    		//countOfChar中元素为-1的是下标对应字符出现不止一次的，为0的是没出现过的，在1~256之间是出现过一次的，值越小出现越早
    		char ch='#';
    		int temp=256;
    		for (int i=0; i<256; i++)
    		{
    			if (countOfChar[i]!=-1&&countOfChar[i]!=0&&countOfChar[i]<=temp)
    			{
    				temp=countOfChar[i];
    				ch=(char)i;
    			}
    		}
    		
    		return ch;
        }
    
    	public static void main(String[] args) 
    	{
    		System.out.println("Hello World!");
    	}
    }