[劍指offer] 第一個隻出現一次的字元

本文首發于我的個人部落格： 尾尾部落

題目描述

在一個字元串(0<=字元串長度<=10000，全部由字母組成)中找到第一個隻出現一次的字元,并傳回它的位置, 如果沒有則傳回 -1.

解題思路

先在hash表中統計各字母出現次數，第二次掃描直接通路hash表獲得次數。也可以用數組代替hash表。

參考代碼

HashMap

import java.util.HashMap;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        int len = str.length();
        if(len == 0)
            return -1;
        HashMap<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < len; i++){
            if(map.containsKey(str.charAt(i))){
                int value = map.get(str.charAt(i));
                map.put(str.charAt(i), value+1);
            }else{
                map.put(str.charAt(i), 1);
            }
        }
        for(int i = 0; i < len; i++){
            if(map.get(str.charAt(i)) == 1)
                return i;
        }
        return -1;
    }
}

           

數組

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        int len = str.length();
        if(len == 0)
            return -1;
        char [] s = str.toCharArray();
        int [] m = new int[256];
        for(int i = 0; i < len; i++){
            m[s[i]]++;
        }
        for(int i = 0; i < len; i++){
            if(m[s[i]] == 1)
                return i;
        }
        return -1;
    }
}