本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖

面試題50：第一個(gè)只出現(xiàn)一次的字符

題目要求：
字符串中第一個(gè)只出現(xiàn)一次的字符。在字符串中找出第一個(gè)只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。

解題思路：
思路1：暴力求解，從前到后依次判斷每個(gè)字符是否只出現(xiàn)一次，時(shí)間復(fù)雜度o(n^2)，空間復(fù)雜度o(1)；
思路2：用空間換時(shí)間。這個(gè)思路可行的前提是題目中所說的“字符”指的是ascii編碼的字符。0-127是7位ASCII碼的范圍，是國際標(biāo)準(zhǔn)。128-255稱為擴(kuò)展ASCII碼，不是國際標(biāo)準(zhǔn)。在C++中，char是1字節(jié)（8bit），能表示256個(gè)不同的字符。而java中，char是unicode編碼，2字節(jié)（16bit）。但本題中，假設(shè)所有字符都可用ascii表示（0-255）。
在上述假設(shè)下，可以申請一個(gè)長度為256的int數(shù)組作為哈希表，占用空間1kB，用它來記錄字符出現(xiàn)的次數(shù)。第一掃描字符串，修改對應(yīng)字符的次數(shù)；第二遍掃描，當(dāng)遇到在數(shù)組中對應(yīng)值為1的字符，即得到所求，時(shí)間復(fù)雜度o(n)。

package chapter5;

/**
 * Created with IntelliJ IDEA
 * Author: ryder
 * Date  : 2017/8/13
 * Time  : 15:32
 * Description:第一次只出現(xiàn)一次的字符
 **/
public class P243_FirstNotRepeatingChar {
    //暴力求解，時(shí)間復(fù)雜度o(n^2),空間復(fù)雜度o(1)
    public static char firstNotRepeatingChar(String str){
        //此處，\77表示ascii為77的字符(即?),用于表征沒有只出現(xiàn)一次的字符
        if(str==null||str.length()==0)
            return '\77';
        for(int i=0;i<str.length()-1;i++){
            char temp = str.charAt(i);
            for(int j=0;j<=str.length();j++){
                if(j==i)
                    continue;
                if(j==str.length())
                    return temp;
                if(temp==str.charAt(j))
                    break;
            }
        }
        return '\77';
    }
    //引入哈希表，用空間換時(shí)間。時(shí)間復(fù)雜度o(n),空間占用1kB
    public static char firstNotRepeatingChar2(String str){
        //使用這個(gè)數(shù)組記錄字符出現(xiàn)次數(shù)
        int[] times = new int[256];
        for(int i=0;i<str.length();i++)
            times[str.charAt(i)]++;
        for(int i=0;i<str.length();i++){
            if(times[str.charAt(i)]==1)
                return str.charAt(i);
        }
        return '\77';
    }
    public static void main(String[] args){
        System.out.println(firstNotRepeatingChar("abaccdeff"));
        System.out.println(firstNotRepeatingChar2("abaccdeff"));

    }
}

運(yùn)行結(jié)果

b
b