जावा: प्रीफिक्स्ड स्ट्रिंग्स (ऐरेलिस्ट्स) की ट्रिकी सॉर्टिंग

Question

(कोई नेटवर्किंग ज्ञान आवश्यक नहीं है। यह पूरी तरह से स्ट्रिंग और सूचियां है)।

कहें कि मेरे पास एक कार्य है, जो स्ट्रिंग आईपीवी 4 बिंदीदार पते की एक सूची स्वीकार करता है, और उन्हें आरोही क्रम में टाइप करता है। (वर्णमाला नहीं, सही आईपी लंबे प्रारूप सॉर्टिंग)। आइए इसे कॉल करें:

public static ArrayList<String> sortListOfIpv4s(ArrayList<String> unsortedIPv4s); 

यह फ़ंक्शन पहले से ही सही तरीके से काम करता है। एक इनपुट को देखते हुए:

192.168.1.1, 8.8.8.8, 4.5.6.7, 244.244.244.244, 146.144.111.6 

यह उत्पादन सूची जाएगा:।

4.5.6.7, 8.8.8.8, 146.144.111.6, 192.168.1.1, 244.244.244.244 

(चलो यह जगह में सूची को संशोधित करने या एक नई सूची वापसी करना चाहिए कि क्या पर एक बहस में नहीं यह सिर्फ रिटर्न एक । नई सूची इसके अलावा, समारोह, क्योंकि कई कारणों से संशोधित नहीं किया जा सकता)

लेकिन, मेरा इनपुट सूची इस प्रकार है:।

e192.168.1.1, f8.8.8.8, e4.5.6.7, f244.244.244.244, e146.144.111.6 

जब मैं उपसर्ग (केवल ई या एफ में से एक, अनिवार्य रूप से वैकल्पिक नहीं) को हटाता हूं और सॉर्टिंग फ़ंक्शन को पास करने के लिए एक साफ़ सरणी बना देता हूं, तो मैं उपसर्ग जानकारी खो देता हूं। क्या मैं चाहूँगा प्रकार का एक उत्पादन है:

e4.5.6.7, f8.8.8.8, e146.144.111.6, e192.168.1.1, f244.244.244.244 

असल में, छँटाई करने से पहले, जो कुछ भी उपसर्ग अवर्गीकृत सूची में प्रत्येक तत्व के लिए मौजूद थे, एक ही उपसर्ग अनुसार क्रमबद्ध में तत्वों को फिर से जोड़ दिये जाने की आवश्यकता है सूची।

चेतावनियां:

• एक आईपी पता मूल सूची में दोहरा सकते हैं, दो बार
• की एक अधिकतम जब दो बार दोहरा, दो तत्वों में से प्रत्येक के एक ही उपसर्ग होगा, इसकी गारंटी
• छंटाई एल्गोरिदम डुप्लिकेट को नहीं हटाएगा।

कृपया थोड़ा एल्गोरिदमिक सहायता कृपया? (याद रखें, हमारे पास पहले से एक ऐसा फ़ंक्शन है जो स्वच्छ आईपीवी 4 स्ट्रिंग सरणीसूची को सॉर्ट कर सकता है)।

Answer 1

सॉर्टिंग फ़ंक्शन में पास करने से पहले उपसर्ग को न हटाएं। इसके बजाय, sortListOfIpv4s विधि में, हमेशा s.substring(1) का उपयोग करके स्ट्रिंग्स की तुलना करें, जो आपको उपसर्ग के बिना पूरी स्ट्रिंग देगा, और परिणामस्वरूप क्रमबद्ध सरणी में s जोड़ें।

तो sortListOfIpv4s एक ब्लैक बॉक्स है और आप एक Mapprefix-free IP -> prefix से में पहले से उपसर्ग मुक्त स्ट्रिंग्स पारित करने के लिए है, तो आप उपसर्गों को कैश कर सकता है की आवश्यकता है:

Map<String, String> prefixMap = new HashMap<String, String>(); 
for (String ip : unsortedIPv4s) { 
    prefixMap.put(ip.substring(1), ip.substring(0, 1)); 
} 

तरह

तो और ठीक हो उपसर्गों Map से:

List<String> sortedIPV4s = sortListOfIpv4s(unsortedIPv4s); 
for (String ip : sortedIPV4s) { 
    String prefix = prefixMap.get(ip); 
    String originalIp = prefix + ip; 
} 

Answer 2

आपकी विधि किसी भी उपसर्ग को स्ट्रिंग के अंत तक ले जा सकती है, सूची को सॉर्ट कर सकती है, और फिर स्ट्रिंग्स के माध्यम से फिर से जा सकती है और उपसर्ग को अंत में शुरुआत से ले जा सकती है।

Answer 3

आप तुलनाकारी को लागू कर सकते हैं:

public class IpComparator implements Comparator<String> { 
    @Override 
    public int compare(String ipA, String ipB) { 
     return doComparison(ipA.substring(1), ipB.substring(1)); 
    } 
} 

तो आप इसका इस्तेमाल कर सकते हैं:

return Collections.sort(unsortedIPv4s, new IpComparator());