查找字符串中的第一個非重複字符

Question

我正在寫一個方法來查找字符串中的第一個非重複字符。我看到這個方法在以前的計算器問題

public static char findFirstNonRepChar(String input){ 
char currentChar = '\0'; 
int len = input.length(); 
for(int i=0;i<len;i++){ 
    currentChar = input.charAt(i); 
    if((i!=0) && (currentChar!=input.charAt(i-1)) && (i==input.lastIndexOf(currentChar))){ 
     return currentChar; 
    } 
} 
return currentChar; 
} 

我想出了一個解決方案使用哈希表，我有兩個for循環（不嵌套），我通過串在一個循環interate的每一次出現的寫下來字母（例如在蘋果中，a會有1，p會有2等），然後在第二個循環中，我通過散列表來交流，看看哪一個先計數1。上述方法對我所提出的方法有什麼好處？我對Java新手有兩個循環（沒有嵌套）阻礙了時間複雜性。這兩種算法都應該有O（n）對嗎？與這兩種解決方案相比，這個問題還有另一種更快，更簡單的空間複雜算法嗎

Answer 1

當您詢問您的代碼是否來自O(n)或不是，我認爲不是，因爲在for循環中，您打電話給lastIndexOf，最壞的情況是O(n)。所以它是從O(n^2)。

關於你的第二個問題：有兩個沒有嵌套的循環，也使它從O(n)。

如果您輸入字符串假定非Unicode字符，而大寫或小寫字符被認爲是不同的，下面將與O（N）做到這一點，並支持所有ASCII碼從0到255：

public static Character getFirstNotRepeatedChar(String input) { 

    byte[] flags = new byte[256]; //all is initialized by 0 

    for (int i = 0; i < input.length(); i++) { // O(n) 
     flags[(int)input.charAt(i)]++ ; 
    } 

    for (int i = 0; i < input.length(); i++) { // O(n) 
     if(flags[(int)input.charAt(i)] == 1) 
      return input.charAt(i); 
    } 

    return null; 
} 

由於康斯坦丁·基亞斯提示關於溢出，如果你輸入的字符串超過256個字符，你可以改變從byte[]flags陣列的類型int[]或long[]防止byte類型的溢出。

希望這會有所幫助。

Answer 2

好吧我最初誤解了這個問題，所以這裏有一個新的解決方案。我相信這是O（n）。 HashSet的contains(Object)是O（1），所以我們可以利用它並避免第二個循環。基本上，如果我們以前從未見過特定的char，我們將其添加到validChars作爲潛在的候選人返回。然後我們再次看到它，我們將它添加到invalidChars的垃圾桶中。這可以防止再次添加字符。在循環結束時（無論你做什麼，你的都有循環至少一次），你將有一個validChars哈希集和n元素的數量。如果沒有，那麼它將返回Character類中的null。這有一個明顯的優勢，因爲char班沒有好的方式來回報可怕的結果。

public static Character findNonRepeatingChar(String x) 
{ 
    HashSet<Character> validChars = new HashSet<>(); 
    HashSet<Character> invalidChars = new HashSet<>(); 

    char[] array = x.toCharArray(); 
    for (char c : array) 
    { 
     if (validChars.contains(c)) 
     { 
      validChars.remove(c); 
      invalidChars.add(c); 
     } 
     else if (!validChars.contains(c) && !invalidChars.contains(c)) 
     { 
      validChars.add(c); 
     } 
    } 

    return (!validChars.isEmpty() ? validChars.iterator().next() : null); 
} 

Answer 3

你表明該算法是緩慢的：它查找字符串中的每個字符，它基本上意味着對於每個字符，你花你的時間檢查字符串的兩倍！巨大的時間損失。

最好的天真O（n）解決方案基本上保持所有字符的順序插入（所以第一可以找到），並映射到他們的可變整數。當我們完成分析時，我們瀏覽所有條目並返回已註冊的第一個字符，其計數爲1。

對可以使用的字符沒有限制。並且AtomicInteger可用於import java.util.concurrent.atomic.AtomicInteger。

使用Java 8：

public static char findFirstNonRepChar(String string) { 
    Map<Integer,Long> characters = string.chars().boxed() 
      .collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting())); 
    return (char)(int)characters.entrySet().stream() 
      .filter(e -> e.getValue() == 1L) 
      .findFirst() 
      .map(Map.Entry::getKey) 
      .orElseThrow(() -> new RuntimeException("No unrepeated character")); 
} 

不支持Java 8當量：

public static char findFirstNonRepChar(String string) { 
    Map<Character, AtomicInteger> characters = new LinkedHashMap<>(); // preserves order of insertion. 
    for (int i = 0; i < string.length(); i++) { 
    char c = string.charAt(i); 
    AtomicInteger n = characters.get(c); 
    if (n == null) { 
     n = new AtomicInteger(0); 
     characters.put(c, n); 
    } 
    n.incrementAndGet(); 
    } 
    for (Map.Entry<Character, AtomicInteger> entry: characters.entries()) { 
    if (entry.getValue().get() == 1) { 
     return entry.getKey(); 
    } 
    } 
    throw new RuntimeException("No unrepeated character"); 
} 

Answer 4

在兩個迴路（未嵌套）的時間複雜度的情況下，會爲O（n）。

在問題中提到的第二個解決方案可以實現爲：

我們可以使用字符串中的字符作爲鍵地圖和維護他們的計數。以下是算法。

1.從左向右掃描字符串並構造計數映射。

2.再從左到右掃描字符串，並檢查地圖中每個字符的計數，如果發現count爲1的元素，則返回它。

package com.java.teasers.samples; 
import java.util.Map; 
import java.util.HashMap; 
public class NonRepeatCharacter { 
    public static void main(String[] args) { 
     String yourString = "Hi this is javateasers";//change it with your string 
     Map<Character, Integer> characterMap = new HashMap<Character, Integer>(); 
     //Step 1 of the Algorithm 
     for (int i = 0; i < yourString.length(); i++) { 
      Character character = yourString.charAt(i); 
      //check if character is already present 
      if(null != characterMap.get(character)){ 
       //in case it is already there increment the count by 1. 
       characterMap.put(character, characterMap.get(character) + 1); 
      } 
      //in case it is for the first time. Put 1 to the count 
      else 
       characterMap.put(character, 1); 
     } 
     //Step 2 of the Algorithm 
     for (int i = 0; i < yourString.length(); i++) { 
      Character character = yourString.charAt(i); 
      int count = characterMap.get(character); 
      if(count == 1){ 
       System.out.println("character is:" + character); 
       break; 
      } 
     } 
    } 
} 

Answer 5

如果你只在A-Z（小寫爲OP在意見中的要求）範圍內的字符有興趣，你可以使用這種方法，需要每個字符兩位Vs的HashMap的方法最低額外的存儲空間。

/* 
* It works for lowercase a-z 
* you can scale it to add more characters 
* eg use 128 Vs 26 for ASCII or 256 for extended ASCII 
*/ 
public static char getFirstNotRepeatedChar(String input) { 

    boolean[] charsExist = new boolean[26]; 
    boolean[] charsNonUnique = new boolean[26]; 

    for (int i = 0; i < input.length(); i++) { 
     int index = 'z' - input.charAt(i); 
     if (!charsExist[index]) { 
      charsExist[index] = true; 
     } else { 
      charsNonUnique[index] = true; 
     } 
    } 

    for (int i = 0; i < input.length(); i++) { 
     if (!charsNonUnique['z' - input.charAt(i)]) 
      return input.charAt(i); 
    } 

    return '?'; //example return of no character found 
} 

Answer 6

適用於任何類型的角色。

String charHolder; // Holds 
String testString = "8uiuiti080t8xt8t"; 
char testChar = ' '; 
int count = 0; 

for (int i=0; i <= testString.length()-1; i++) { 
    testChar = testString.charAt(i); 

    for (int j=0; j < testString.length()-1; j++) { 
     if (testChar == testString.charAt(j)) { 
      count++; 
     } 
    } 
    if (count == 1) { break; }; 
     count = 0; 
} 

System.out.println("The first not repeating character is " + testChar); 

Answer 7

import java.util.Scanner; 

public class NonRepaeated1 
{ 
    public static void main(String args[]) 
    { 
    String str; 
    char non_repeat=0; 
    int len,i,j,count=0; 

    Scanner s = new Scanner(System.in); 
    str = s.nextLine(); 

    len = str.length(); 

    for(i=0;i<len;i++) 
    { 
     non_repeat=str.charAt(i); 
     count=1; 

     for(j=0;j<len;j++) 
     { 
     if(i!=j) 
     { 
      if(str.charAt(i) == str.charAt(j)) 
      { 
      count=0; 
      break; 
      } 
     } 
     } 

     if(count==1) 
     break; 
    } 
if(count == 1) 
System.out.print("The non repeated character is : " + non_repeat); 

    } 
} 

Answer 8

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

public class getFirstNonRep { 

public static char get(String s) throws Exception { 
    if (s.length() == 0) { 
     System.out.println("Fail"); 
     System.exit(0); 
    } else { 
     Map<Character, Integer> m = new LinkedHashMap<Character, Integer>(); 

     for (int i = 0; i < s.length(); i++) { 
      if (m.containsKey(s.charAt(i))) { 
       m.put(s.charAt(i), m.get(s.charAt(i)) + 1); 
      } else { 
       m.put(s.charAt(i), 1); 
      } 
     } 
     for (Map.Entry<Character, Integer> hm : m.entrySet()) { 
      if (hm.getValue() == 1) { 
       return hm.getKey(); 
      } 
     } 
    } 
    return 0; 
} 

public static void main(String[] args) throws Exception { 

    System.out.print(get("Youssef Zaky")); 

    } 

} 

這種解決方案需要更少的空間和更少的時間，因爲我們遍歷字符串一次。

Answer 9

public char firstNonRepeatedChar(String input) { 
    char out = 0; 
    int length = input.length(); 
    for (int i = 0; i < length; i++) { 
     String sub1 = input.substring(0, i); 
     String sub2 = input.substring(i + 1); 
     if (!(sub1.contains(input.charAt(i) + "") || sub2.contains(input 
       .charAt(i) + ""))) { 
      out = input.charAt(i); 
      break; 
     } 
    } 
    return out; 
} 

Answer 10

package com.test.util; 

public class StringNoRepeat { 

    public static void main(String args[]) { 
     String st = "234123nljnsdfsdf41l"; 
     String strOrig=st; 
     int i=0; 
     int j=0; 
     String st1=""; 
     Character ch=' '; 
     boolean fnd=false; 
     for (i=0;i<strOrig.length(); i++) { 


      ch=strOrig.charAt(i); 
      st1 = ch.toString(); 

      if (i==0) 
       st = strOrig.substring(1,strOrig.length()); 
      else if (i == strOrig.length()-1) 
      st=strOrig.substring(0, strOrig.length()-1); 
      else 
       st=strOrig.substring(0, i)+strOrig.substring(i+1,strOrig.length()); 
      if (st.indexOf(st1) == -1) { 
       fnd=true; 
       j=i; 
       break; 
      } 
     } 
     if (!fnd) 
      System.out.println("The first no non repeated character"); 
     else 
      System.out.println("The first non repeated character is " +strOrig.charAt(j)); 


    } 

} 

Answer 11

由於LinkedHashMap的保持插入的代碼

package com.company; 

import java.util.LinkedHashMap; 
import java.util.Map; 
import java.util.Scanner; 

public class Main { 
    public static void main(String[] argh) { 
     Scanner sc = new Scanner(System.in); 
     String l = sc.nextLine(); 
     System.out.println(firstCharNoRepeated(l)); 
    } 

    private static String firstCharNoRepeated(String l) { 
     Map<String, Integer> chars = new LinkedHashMap(); 
     for(int i=0; i < l.length(); i++) { 
      String c = String.valueOf(l.charAt(i)); 
      if(!chars.containsKey(c)){ 
       chars.put(c, i); 
      } else { 
       chars.remove(c); 
      } 
     } 
     return chars.keySet().iterator().next(); 
    } 
} 

Answer 12

幾行命令，爲我工作。

public class FirstNonRepeatingCharacter { 

    final static String string = "cascade"; 

    public static void main(String[] args) { 

     char[] charArr = string.toCharArray(); 

     for (int i = 0; charArr.length > i; i++) { 
      int count = 0; 
      for (int j = 0; charArr.length > j; j++) { 
       if (charArr[i] == charArr[j]) { 
        count++; 
       } 
      } 
      if (count == 1){ 
       System.out.println("First Non Repeating Character is: " + charArr[i]); 
       break; 
      } 
     } 

    } 
}