java - 流中的第一个非重复字符

Question

我对这个问题的回答如下，但是我想知道我是否可以使用这段代码，复杂度如何:

import java.util.LinkedHashMap;
import java.util.Map.Entry;

public class FirstNonRepeatingCharacterinAString {

    private char firstNonRepeatingCharacter(String str) {       
        LinkedHashMap<Character, Integer> hash =
                new LinkedHashMap<Character, Integer>();

        for(int i = 0 ; i< str.length() ; i++)
        {
            if(hash.get(str.charAt(i))==null)
                hash.put(str.charAt(i), 1);
            else
                hash.put(str.charAt(i), hash.get(str.charAt(i))+1);
        }

        System.out.println(hash.toString());

        for(Entry<Character, Integer> c : hash.entrySet())
        {
            if(c.getValue() == 1)
                return c.getKey();
        }

        return 0 ;
    }

    public static void main(String args[])
    {
        String str = "geeksforgeeks";
        FirstNonRepeatingCharacterinAString obj =
                new FirstNonRepeatingCharacterinAString();
        char c = obj.firstNonRepeatingCharacter(str);
        System.out.println(c);
    }
}

Answer 1

你关于你是否“可以使用这段代码”的问题有点模棱两可——如果你写了它，我认为你可以使用它:)

至于复杂度，就是O(n)其中 n是 String 中的字符数.要计算出现的次数，您必须遍历整个 String , 再加上再次迭代它们以找到第一个计数为 1 的.在最坏的情况下，你没有非重复字符，或者唯一的非重复字符是最后一个。无论哪种情况，您都必须遍历整个 String再一次。所以它是O(n+n) = O(n) .

编辑

顺便说一句，您的代码中有一个错误。因为您使用的是插入顺序 LinkedHashMap , 每次调用 put(Character,Integer)导致基础列表的重新排序。您可能应该使用 LinkedHashMap<Character,int[]>相反，并在放置之前检查是否存在 key 。如果它们存在，则仅增加存储在 int[] 中的值。避免通过制作另一个 put 来重新排序 map 称呼。即便如此，结果列表的顺序将与您迭代它的方式相反，因此 第一个 非重复字符将是您在迭代它时找到的最后一个值为 1 的字符。或者，您可以在第一个 for 中反向迭代循环，那么你就不必总是遍历整个 Entry如果第一个非重复字符早于原始字符中的最后一个字符 String 则设置.