劍指offer—-字元流中第一個不重複的字元—-java實現

NO IMAGE

題目描述

請實現一個函式用來找出字元流中第一個只出現一次的字元。例如,當從字元流中只讀出前兩個字元”go”時,第一個只出現一次的字元是”g”。當從該字元流中讀出前六個字元“google”時,第一個只出現一次的字元是”l”。 

輸出描述:
如果當前字元流沒有存在出現一次的字元,返回#字元。

思路:第一個不重複的字元  兩個關鍵點 不重複也就是出現一次,第一個也就是找到將其返回不再找下面的了

兩個輔助空間

(1)HashMap
根據字元放入map中每次將次數加1;

(2)ArrayList
將插入的每個字元放入到list中,list是有順序地存放。遍歷list去map中根據字元找其出現的次數。

import java.util.ArrayList;
import java.util.HashMap;
public class First
{
HashMap<Character,Integer> map = new HashMap<Character,Integer>();//存放字元和其出現的次數
ArrayList<Character> list = new ArrayList<Character>();//存放字元
//把字元存對應的次數在map中更新,並把字元按照出現順序存放在list中
public void Insert(char ch)
{
//判斷map中是否已經包含要插入的字元,如果已經包含則將其次數 1
if(map.containsKey(ch))
{
map.put(ch,map.get(ch) 1);//map.get(ch)是根據key得到value的值
}
else
{
map.put(ch,1);//如果map中還沒有包含,則把ch放入map中,並將其值設為1;
}
list.add(ch);//將ch放入list中,便於根據list中儲存的ch到map中去查詢出現次數
}
//遍歷list去map中尋找出現的次數
public char FirstAppearingOnce()
{
char ch ='#';
for (int i = 0; i < list.size(); i  )
{
if(map.get(list.get(i)) == 1)
{
ch = list.get(i);
break;
}
}
return ch;
}
}