字符串唯一字符

-1

實現算法以確定字符串是否具有所有唯一字符。如果你不能使用額外的數據結構怎麼辦？字符串唯一字符

2010-04-07 Jony

你有什麼這麼遠嗎？ – 2010-04-07 02:21:24

請將作業問題標記爲家庭作業 – 2010-04-07 02:22:08

@brian它不是一個家庭作業它是網站上的技術問題之一 @michael它只是任何字符串就像說「abcedef」 – Jony 2010-04-07 02:26:05

如果您可以使用一些輔助內存，那麼您需要的只是一小段位（由字符的數字代碼索引）（如果您的字符是4字節的Unicode字符，那麼您可能需要一個哈希映射代替;-）。從0處的所有位開始：從開始掃描字符串 - 每次，如果與當前字符對應的位已經爲1，則發現重複 - 否則，沒有重複，將該位設置爲1。是O（N）。

如果你不能分配任何額外的內存，但可以改變字符串，排序字符串，然後做一個通過檢查相鄰的重複是最好的，你可以做，O（N日誌N）。

如果您不能分配額外的內存並且無法更改字符串，則需要進行O（N平方）檢查，其中檢查每個字符與以下所有字符。

來源

2010-04-07 02:32:49

for each character in the string 
    if any subsequent character matches it 
    fail 
succeed

來源

2010-04-07 02:23:50 WhirlWind

我認爲我們需要排序的字符串是不是一個非常有效的解決方案 – Jony 2010-04-07 02:27:24

爲什麼你需要對它進行分類？ – WhirlWind 2010-04-07 02:28:41

哦你的意思是將每個字符與字符串的所有其他字符進行比較，但這會導致O（n * n）的複雜度。 – Jony 2010-04-07 02:33:37

一個可行的辦法 - 你可以提取字符串轉換爲字符數組，數組排序，然後遍歷它，檢查是否下一個字符是等於當前的一個。

來源

2010-04-07 02:23:51

我們可以通過爲每個字符分配一個素數來做到這一點，並將其乘以每個找到的字符。然後在每一個字符檢查，如果值是由分配給該字符或不是數整除..

來源

2011-09-06 12:00:02 partik

-1

public static boolean isUniqueChars(String str) { 
    int checker = 0; 
    for (int i = 0; i < str.length(); ++i) { 
     int val = str.charAt(i) - 'a'; 
     if ((checker & (1 << val)) > 0) 
      return false; 
     checker |= (1 << val); 
    } 
    return true; 
}

來源

2012-02-16 04:43:45 Manish

你應該評論你的代碼。 – alestanis 2012-10-29 20:46:56

你能解釋你的解決方案嗎？ – Adil 2012-11-19 09:37:30

你是以什麼理由決定一個整數可以覆蓋所有的Unicode字符甚至ASCII字符？字符串只有小寫字母的假設不正確 – Mina 2014-11-11 22:24:03

答案在C程序

int is_uniq(char *str) 
{ 
    int i = 0, flag = 0, value = 0; 
    for(i = 0; i < strlen(str); i++) { 
     value = str[i] - 'a'; 
     if(flag & (1 << value)) { 
      return 0; 
     } 
     flag |= (1 << value); 
    } 
    return 1; 
}

來源

2012-12-01 14:32:44 senthilkumar

字符串「AbcdDEfh」如何？使用str [i] - 'a'有什麼意義？ – 2013-07-22 06:56:38

import java.io.*; 

public class uniqueChar 
{ 
    boolean checkUniqueChar(String strin) 
    { 
     int m; 
     char []str=strin.toCharArray(); 
     java.util.Arrays.sort(str); 
     for(int i=0;i<str.length-1;i++) 
     { 
      if(str[i]==str[i+1]) 
       return false; 
     } 
     return true; 
    } 

    public static void main(String argv[]) throws IOException 
    { 
     String str; 
     System.out.println("enter the string\n"); 
     InputStreamReader in=new InputStreamReader(System.in); 
     BufferedReader bin=new BufferedReader(in); 
     str=bin.readLine(); 
     System.out.println(new uniqueChar().checkUniqueChar(str)); 
    } 
}

來源

2013-02-11 13:45:25 dod

由partik（描述的方法素基於此theorem）。這是O（N）。

# one prime per letter 
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101] 

starting_byte = ?a.ord 
primes_product = 1 

ARGV[0].each_byte do |byte| 
    current_prime = primes[byte - starting_byte] 
    if primes_product % current_prime == 0 
     puts "Not unique" 
     exit 
    else 
     primes_product = primes_product * current_prime 
    end 
end 

puts "Unique"

來源

2013-04-17 06:42:36 Thomas

我來到這個線程對於類似的問題，並結束了與C＃中的以下解決方案：

 var data = "ABCDEFGADFGHETFASAJUTE"; 

     var hash = new Dictionary<char, int>(); 

     foreach (char c in data) 
     { 
      if (hash.ContainsKey(c)) 
      { 
       hash[c] += 1; 
      } 
      else 
      { 
       hash.Add(c, 1); 
      } 
     } 

     var Characters = hash.Keys.ToArray(); 
     var Frequencies = hash.Values.ToArray();

來源

2013-12-10 04:29:38 mathsRuinedme

字符串唯一字符

回答

相關問題