第一个非重复的字符

我要回答的问题是这样的，但我想知道如果我可以使用此代码，会是怎样的复杂性：第一个非重复的字符

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); 
    } 
}

来源

2017-05-09 DavidB

*我想知道我是否可以使用此代码。*这是版权问题吗？ – shmosel

这段代码的复杂性是O（n）。但是你的代码似乎没有返回标题中提到的内容。 – arunk2

我只是想知道，如果这个解决方案有效。它不是一个版权问题。 – DavidB

你有关的问题是否你“可以使用此代码”是一个小暧昧 - 如果你写的，我还以为你可以用它:)

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

编辑

。在你的代码中的错误，顺便说一句。由于您正在使用插入订单LinkedHashMap，因此每次调用put(Character,Integer)都会导致对基础列表进行重新排序。您应该使用LinkedHashMap<Character,int[]>来替代，并且在放置之前检查密钥的存在。如果它们存在，那么只需增加存储在int[]中的值，以避免通过拨打另一个put呼叫来重新定位地图。即使如此，结果列表的排列方式也会与您遍历它的方式相反，因此非重复字符将是迭代其值时为1的最后一个字符。或者，您也可以迭代在第一个for循环中相反，那么如果第一个非重复字符比最初的String中的最后一个字符快，则您不必总是遍历整个Entry集合。

来源

2017-05-09 23:48:51 CodeBlind

第一个非重复的字符

回答

相关问题