[剣指Offer]初めて出てくる文字

タイトル
文字列を与えて、最初の重複しない文字abbcad->cを求めます
問題解決の考え方:
今日のお昼の面接で2番目の問題は、文字列の各文字を最初からスキャンすることです.ある文字にアクセスすると、この文字と後ろの各文字を比較します.後に重複する文字が見つからない場合、その文字は一度しか現れない文字です.文字列にn文字がある場合、各文字は後のO(n)文字列と比較される可能性があるため、この考え方の時間的複雑度はO(n^2)である.
これは最良の方法ではなく,より良い方法の時間的複雑さはO(n)であるべきである.
それから私は帰ってよく考えて、思考を広げて補助容器の考え方を借りることができるかどうかを考えて、それからJavaの中のデータ容器を採用して各文字の出現回数を保存します.この問題を解決するために、LinkedHashMapのキー(key)は文字であり、値(value)はその文字の出現回数であると定義することができる.
考え方:
文字列を最初から2回スキャンする必要があります.文字列を最初にスキャンするたびに、ハッシュテーブルの対応するアイテムに1文字ずつスキャンします.次に2回目のスキャンでは、1文字をスキャンするたびにハッシュテーブルからその文字が現れる回数が得られます.このように最初に1回しか現れない文字は、要求に合致する出力です.
時間複雑度分析:
最初のforループでハッシュテーブルで1文字の出現回数を更新する時間的複雑度はO(n)である.2番目のfor時間複雑度もO(n)であり,2つのforサイクルは最大2 n回実行され,合計時間複雑度はO(n)であり,問題の要求に合致する.
コード実装:

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        System.out.println(get("alibaba"));
        System.out.println(get("taobao"));
        System.out.println(get("aabbccd"));
        System.out.println(get("ddbbdd"));
        System.out.println(get("ahsdkdhask"));
    }

    /** *             * @param s        * @return         ，           ，  null */
    public static Character get(String s) {
        //       
        if (s == null || s.length() < 1) {
            //     
            throw new IllegalArgumentException("should not be null or empty");
        }
        Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
        int len = s.length();

        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            Integer already = map.get(c);
            already = (already == null) ? 0 : already;
            map.put(s.charAt(i), ++already);
        }

        Set<Map.Entry<Character, Integer>> entries = map.entrySet();
        for (Map.Entry<Character, Integer> entry : entries) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return null;
    }
}

nullが返されていない場合は、実行結果が正しい.