【劍指offer】第一個隻出現一次的字元

轉載請注明出處：

<dl></dl>

<dt>題目描述：</dt>

<dd></dd>

在一個字元串(1&lt;=字元串長度&lt;=10000，全部由大寫字母組成)中找到第一個隻出現一次的字元。

<dt>輸入：</dt>

輸入有多組資料

每一組輸入一個字元串。

<dt>輸出：</dt>

輸出第一個隻出現一次的字元下标，沒有隻出現一次的字元則輸出-1。

<dt>樣例輸入：</dt>

<dt>樣例輸出：</dt>

    處理字元串中重複或者次數出現等問題，最常用的就是哈希表，用字元串中的字元作為key，字元出現次數作為value，假定隻有ASCII碼範圍内的字元，則可以開辟一個256大小的int數組，将每個字元（key）映射到該數組的對應位置上，計算每次出現的次數即可，周遊一次字元串，計算每個字元出現的次數，儲存在int數組的對應位置上，第二次周遊字元串，若第一次出現某個字元對對應到的哈希表的對應位置處的元素為1，則該字元便是第一個隻出現一次的字元，如果我們是周遊哈希表（int數組），則找到的哈希表中的第一個元素為1的位置對應的字元為字元串中第一個最小的隻出現一次的字元。時間複雜度為O（n），需要額外的256個int空間來輔助，可以看做空間複雜度為O（1）。

    另外，如果要省空間，我們可以bitmap算法，用兩個位來表示對應字元出現的次數，出現0次，則為00，出現一次則為01，出現2次及以上，都維持在10即可。

    另外，有一點需要注意，char的範圍在-128-127，unsigned char的範圍才是在0-255，是以ASCII值在128-255之間的字元，如果儲存為了char型，其轉化為int值的範圍是在-128--1之間，這點在下面的代碼中有展現。

    下面給出用簡單哈希表AC的代碼（根據題目要求和測試要求分别寫了兩個函數）：

/**************************************************************

<code>    </code><code>Problem: 1283</code>

<code>    </code><code>User: mmc_maodun</code>

<code>    </code><code>Language: C</code>

<code>    </code><code>Result: Accepted</code>

<code>    </code><code>Time:10 ms</code>

<code>    </code><code>Memory:912 kb</code>

<code>****************************************************************/</code>