जावा में एक स्ट्रिंग में किसी चरित्र की फ़्रिक्वेंसी खोजने का कुशल तरीका: ओ (एन)

Question

हाल के एक साक्षात्कार में मुझे नीचे दिए गए कार्यक्रम को लिखने के लिए कहा गया था। उस वर्ण का पता लगाएं जिसकी आवृत्ति दी गई स्ट्रिंग में न्यूनतम है? तो मैंने charAt का उपयोग करके स्ट्रिंग के माध्यम से पुनरावृत्ति करके और चरित्र को हैश मैप में कुंजी के रूप में संग्रहीत करने और अवसरों की संख्या के रूप में इसकी कीमत के रूप में संग्रहित करने की कोशिश की। अब मुझे सबसे कम तत्व खोजने के लिए मानचित्र पर फिर से शुरू करना होगा।

क्या ऐसा करने का एक और अधिक प्रभावी तरीका है क्योंकि स्पष्ट रूप से ऊपर वाला एक अनुमान है कि मुझे लगता है।

अद्यतन और एक अन्य समाधान

कुछ विचार प्रक्रिया और जवाब के बाद मुझे लगता है कि सबसे अच्छा समय है कि हो सकता है हे (एन) है। पहले पुनरावृत्ति में हमें चरित्र द्वारा स्ट्रिंग चरित्र के माध्यम से पुनरावृत्ति करना होगा और फिर अपनी आवृत्ति को विशिष्ट स्थिति (एक चरित्र एक int) पर एक ऐरे में संग्रहीत करना होगा और उसी समय दो अस्थायी चर होते हैं जो कम से कम गिनती और संबंधित चरित्र बनाए रखते हैं इसलिए जब मैं अगले चरित्र पर जाता हूं और इसकी आवृत्ति को एआर [char] = arr [char] +1 में संग्रहीत करता हूं, उसी समय मैं जांच करूंगा कि अस्थायी चर के पास इस मान से अधिक मूल्य है, यदि हां तो अस्थायी विविधता यह मूल्य होगी और यह भी एक होगा। इस तरह से मुझे लगता है कि हमें सबसे छोटा खोजने के लिए दूसरी पुनरावृत्ति की आवश्यकता नहीं है और कोई सॉर्टिंग आवश्यक नहीं है मुझे लगता है कि

.... वाट कहें? या कोई और समाधान

Answer 1

मैं हैश मानचित्र के बजाय एक सरणी का उपयोग करता हूं। अगर हम एसीआईआई तक सीमित हैं, तो यह केवल 256 प्रविष्टियां है; अगर हम यूनिकोड, 64k का उपयोग कर रहे हैं। किसी भी तरह से एक असंभव आकार नहीं है। इसके अलावा, मैं नहीं देखता कि आप अपने दृष्टिकोण पर कैसे सुधार कर सकते हैं। मैं इसे और अधिक कुशल बनाने के लिए कुछ चालाक चाल के बारे में सोचने की कोशिश कर रहा हूं लेकिन मैं किसी के साथ नहीं आ सकता।

मुझे लगता है कि उत्तर हमेशा वर्णों की पूरी सूची बनने जा रहा है: उन सभी का उपयोग जो शून्य बार उपयोग किए जाते हैं।

अद्यतन

यह शायद सबसे कुशल यह जावा में हो सकता है के लिए clost है। सुविधा के लिए, मुझे लगता है कि हम सादे असीसी का उपयोग कर रहे हैं।

public List<Character> rarest(String s) 
{ 
    int[] freq=new int[256]; 

    for (int p=s.length()-1;p>=0;--p) 
    { 
    char c=s.charAt(p); 
    if (c>255) 
     throw new UnexpectedDataException("Wasn't expecting that"); 
    ++freq[c]; 
    } 
    int min=Integer.MAX_VALUE; 
    for (int x=freq.length-1;x>=0;--x) 
    { 
    // I'm assuming we don't want chars with frequency of zero 
    if (freq[x]>0 && min>freq[x]) 
     min=freq[x]; 
    } 
    List<Character> rares=new ArrayList<Character>(); 
    for (int x=freq.length-1;x>=0;--x) 
    { 
    if (freq[x]==min) 
     rares.add((char)x); 
    } 
    return rares; 
} 

सूची आवृत्ति के अनुसार क्रमबद्ध रूप में तुम जाओ जिस तरह से अधिक अक्षम हो सकता है, क्योंकि यह करने के लिए फिर से तरह हर बार जब आप एक चरित्र की जांच करनी होगी जा रहा है रखने के लिए किसी भी प्रयास।

आवृत्तियों की सूची को क्रमबद्ध करने का कोई भी प्रयास अधिक अक्षम होगा, क्योंकि पूरी सूची को क्रमबद्ध करने से स्पष्ट रूप से धीमा होने वाला है।

स्ट्रिंग को सॉर्ट करना और फिर गिनती धीमी हो रही है क्योंकि यह गणना गिनती से अधिक महंगी होगी।

तकनीकी रूप से, यह एक ऐरेलिस्ट के बजाय अंत में एक सरल सरणी बनाने के लिए तेज़ होगा, लेकिन ऐरेलिस्ट थोड़ा और पठनीय कोड बनाता है।

इसे तेजी से करने का एक तरीका हो सकता है, लेकिन मुझे संदेह है कि यह इष्टतम समाधान के करीब है। मैं निश्चित रूप से यह देखने में दिलचस्पी लेता हूं कि किसी के पास बेहतर विचार है या नहीं।

Answer 2

मुझे लगता है कि आपका दृष्टिकोण सिद्धांत में सबसे कुशल (ओ (एन)) है। हालांकि अभ्यास में इसे काफी मेमोरी की आवश्यकता होती है, और शायद यह बहुत धीमी है।

संभवतः यह और अधिक कुशल, एक चार सरणी स्ट्रिंग परिवर्तित सरणी सॉर्ट, और फिर एक सरल पाश का उपयोग कर आवृत्तियों की गणना करने के (कम से कम यह कम स्मृति का उपयोग करता है)। हालांकि, सिद्धांत में यह कम कुशल (ओ (एन लॉग एन)) सॉर्टिंग के कारण है (जब तक कि आप एक अधिक कुशल सॉर्ट एल्गोरिदम का उपयोग न करें)।

टेस्ट मामला:

import java.util.Arrays; 

public class Test { 

    public static void main(String... args) throws Exception { 
     //  System.out.println(getLowFrequencyChar("x")); 
     //  System.out.println(getLowFrequencyChar("bab")); 
     //  System.out.println(getLowFrequencyChar("babaa")); 
     for (int i = 0; i < 5; i++) { 
      long start = System.currentTimeMillis(); 
      for (int j = 0; j < 1000000; j++) { 
       getLowFrequencyChar("long start = System.currentTimeMillis();"); 
      } 
      System.out.println(System.currentTimeMillis() - start); 
     } 

    } 

    private static char getLowFrequencyChar(String string) { 
     int len = string.length(); 
     if (len == 0) { 
      return 0; 
     } else if (len == 1) { 
      return string.charAt(0); 
     } 
     char[] chars = string.toCharArray(); 
     Arrays.sort(chars); 
     int low = Integer.MAX_VALUE, f = 1; 
     char last = chars[0], x = 0; 
     for (int i = 1; i < len; i++) { 
      char c = chars[i]; 
      if (c != last) { 
       if (f < low) { 
        if (f == 1) { 
         return last; 
        } 
        low = f; 
        x = last; 
       } 
       last = c; 
       f = 1; 
      } else { 
       f++; 
      } 
     } 
     if (f < low) { 
      x = last; 
     } 
     return (char) x; 
    } 

} 

Answer 3

मैं इसे निम्नलिखित तरीके से करना चाहते हैं के रूप में यह कोड आवश्यक कम से कम लाइनों शामिल है: "_"
:

चरित्र आप चाहते हैं की आवृत्ति जानना चाहता हूँ करने के लिए स्ट्रिंग "this_is_a_test"

String testStr = "this_is_a_test"; 
String[] parts = testStr.split("_"); //note you need to use regular expressions here 
int freq = parts.length -1; 

आप पा सकते हैं अजीब बातें होती हैं, तो स्ट्रिंग शुरू होता है या प्रश्न में चरित्र के साथ समाप्त होता है, लेकिन मैं यह करने के लिए छोड़ देंगे आप इसके लिए परीक्षण करने के लिए।

Answer 4

एक स्ट्रिंग में वर्णों की आवृत्ति खोजने की प्रक्रिया बहुत आसान है।
उत्तर के लिए मेरे कोड देखें।

import java.io.*; 
public class frequency_of_char 
{ 
    public static void main(String args[])throws IOException 
    { 
     BufferedReader in=new BufferedReader(new InputStreamReader(System.in)); 
     int ci,i,j,k,l;l=0; 
     String str,str1; 
     char c,ch; 
     System.out.println("Enter your String"); 
     str=in.readLine(); 
     i=str.length(); 
     for(c='A';c<='z';c++) 
     { 
      k=0; 
      for(j=0;j<i;j++) 
      { 
       ch=str.charAt(j); 
       if(ch==c) 
        k++; 
      } 
      if(k>0) 
      System.out.println("The character "+c+" has occured for "+k+" times"); 
     } 
    } 
} 

Answer 5

HashMap के माध्यम से पुनरावृति करने के बाद जरूरी बुरा नहीं है। यही कारण है कि केवल O(h) हो जाएगा जहां h HashMap की लंबाई है - अद्वितीय वर्णों की संख्या - जो इस मामले में हमेशा n से कम या उसके बराबर हो जाएगा। उदाहरण के लिए "aaabbc", h = 3 तीन अद्वितीय पात्रों के लिए। लेकिन, h संभावित पात्रों की संख्या से सख्ती से कम है: 255, यह स्थिर है। तो, अपने बड़े ओह O(n+h) जो वास्तव में O(n)h के बाद से स्थिर है किया जाएगा। मैं किसी भी एल्गोरिथ्म है कि एक बेहतर बड़ा, ओह, आप जावा विशिष्ट अनुकूलन का एक समूह है की कोशिश कर सकते हो सकता है के बारे में पता नहीं है, लेकिन है कि यहाँ कहा एक सरल एल्गोरिथ्म मुझे लगता है कि सबसे कम आवृत्ति के साथ char पाता लिखा है। यह "aaabbc" इनपुट से "c" देता है।

import java.util.HashMap; 
import java.util.Map; 

public class StackOverflowQuestion { 

public static void main(String[] args) { 
    // TODO Auto-generated method stub 

    System.out.println("" + findLowestFrequency("aaabbc")); 

} 

public static char findLowestFrequency(String input) { 

    Map<Character, Integer> map = new HashMap<Character, Integer>(); 

    for (char c : input.toCharArray()) 

     if (map.containsKey(c)) 
      map.put(c, map.get(c) + 1); 
     else 
      map.put(c, 0); 

    char rarest = map.keySet().iterator().next(); 

    for (char c : map.keySet()) 

     if (map.get(c) < map.get(rarest)) 
      rarest = c; 

    return rarest; 

} 

}