java - 使用 LinkedHashMap 的字符串中的第一个唯一字符

Question

给定一个字符串，找到其中的第一个非重复字符并返回它的索引。如果不存在，返回-1。

例子:

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

在我的解决方案中，我可以找到角色本身，但我希望获得角色的索引!我将如何更改我的代码以使用 LinkedHashMap 获取索引？提前谢谢你。

public static void firstNonRepeatingString(String str) {
    LinkedHashMap<Character, Integer> lhm = new LinkedHashMap<>();
    char[] charArray = str.toCharArray();
    for (char character : charArray) {
        if (lhm.get(character) == null) {
            lhm.put(character, 1);
        } else {
            lhm.put(character, lhm.get(character) + 1);
        }
    }

    for (Map.Entry<Character, Integer> entry : lhm.entrySet())
        if (entry.getValue() == 1) {
            System.out.print(entry.getKey());
            break;
        }
}

firstNonRepeatingString("aaabcccddeggf"); 

这将打印 b，但我想打印 3。

Answer 1

哈希集

该集合仅用于避免再次计算已经看到的字符。该集合不需要遵守插入顺序，因为它的目标只是检查元素是否存在。为此，HashSet 是一个合适的选择。

StringUtils 确实有一些很好的实用程序，其中之一是计算源字符串中单个字符/字符串的出现次数。

因为您希望第一个字符是唯一的，如果该元素不存在于 set 中并且 countMatches 返回 1，您得到了你的结果。

如果未找到唯一值，则返回 -1 (例如) 作为在字符串中未找到唯一值的表示。

public static int firstNonRepeatingCharIndex(String str) 
{
   HashSet<Character> dupSet = new HashSet<>();   //duplicates list
   for(char c : str.toCharArray()) 
   {
      if (dupSet.contains(c))
          continue;
      if (StringUtils.countMatches(str, c) == 1)
          return str.indexOf(c);
      dupSet.add(c);
   }
   return -1;
}

这避免了:

• 在找到结果后，对所有字符进行无用的迭代。
• 已经看到的字符的无用过程。
• 无用的 map 创建及其相关操作，例如聚合。

---

HashSet + LinkedHashSet

对于这个特定问题，这不是必需的，但以防万一您想知道哪些是唯一值及其顺序，因此您想使用两个 Set 迭代到最后可能是一种选择。

public static int firstNonRepeatingCharIndex(String str) 
{
   LinkedHashSet<Character> lSet = new LinkedHashSet<>();
   HashSet<Character> dupSet = new HashSet<>();   //duplicates list

   for(char character : str.toCharArray()) 
   {
      if (dupSet.contains(character))  //exists in duplicates, continue
          continue;         
      if (lSet.contains(character))   //exists in the linkedSet, add to duplicates
          dupSet.add(character);          
      else
          lSet.add(character);        //first time seen, add to linkedSet
   } 

   lSet.removeAll(dupSet);          //remove all duplicates 
   if (lSet.isEmpty())
        return -1;

   return str.indexOf(lSet.iterator().next());  
}

---

LinkedHashMap

仅当需要完整 map 、获取统计信息或其他任何内容时。

请注意，无需添加/修改条目。如果key不在map中，我们直接设置出现次数。

public static int firstNonRepeatingCharIndex(String str) 
{
  LinkedHashMap <Character , Integer> lhm = new LinkedHashMap<>();
  int c = 0, index = -1;
  for(char character : str.toCharArray()) 
  {
     if (lhm.get(character) == null)
     {
        int oc = StringUtils.countMatches(str,character);
        if (oc==1 && index<0)
           index = c;           //will only bet set once
        lhm.put(character, oc);
      }            
      if (index<0)     
        c++;                   //no need for this after index is found
   } 
   //showStatsOfMap(lhm); ?
   return index;
}

---

如果你根本不需要 map 的结果(这让你想知道为什么这里有 map )

public static int firstNonRepeatingCharIndex(String str) 
{
   LinkedHashMap <Character , Integer> lhm = new LinkedHashMap<>();
   int c = 0;
   for(char character : str.toCharArray()) 
   {
      if (lhm.get(character)==null)
      {
          int oc = StringUtils.countMatches(str,character);
          if (oc == 1)
             return c;
          lhm.put(character, oc);
      }
       c++;
   }    
    //sendNonUniqueMap(lhm); //??? just to make use of it...
    return -1;
 }