एक क्रम में लगातार एक ही शब्द हटाएं


कठिनाई स्तर मध्यम
में अक्सर पूछा FactSet
ऐरे छंटाई धुआँरा तार

समस्या का विवरण

समस्या "एक क्रम में लगातार एक ही शब्द हटाएं" बताता है कि आपको एक दिया गया है सूची n का तार। अगर लगातार दो समान शब्द मौजूद हैं, तो उन दोनों को हटा दें। ऐसी सभी जोड़ियों को हटाने के बाद सूची में छोड़े गए कुल शब्दों / तारों को प्रिंट करें।

एक क्रम में लगातार एक ही शब्द हटाएं

उदाहरण

s[ ] = {ab, aa, aa, bcd, ab}
3
s[ ] = {cpp, cpp, java}
1

स्टैक का उपयोग करना

कलन विधि

  1. की सूची को प्रारंभ करें n तार.
  2. बनाओ धुआँरा डेटा संरचना।
  3. सूची के 0 से आकार तक का पारगमन - 1।
    1. जांचें कि क्या स्टैक खाली है यानी स्टैक का आकार 0 है
      1. स्टैक में सूची में वर्तमान सूचकांक में शब्द को पुश / सम्मिलित करें।
    2. एल्स एक स्ट्रिंग वेरिएबल बनाते हैं और उसमें स्टैक के शीर्ष पर स्ट्रिंग को स्टोर करते हैं।
      1. सूची में वर्तमान सूचकांक में शब्द के साथ स्ट्रिंग चर की तुलना करें, यदि दोनों तार समान हैं।
        1. स्टैक के ऊपर से स्ट्रिंग निकालें।
      2. अगर तार अलग-अलग हों तो।
        1. स्टैक के लिए वर्तमान सूचकांक में स्ट्रिंग पुश करें।
  4. स्टैक का आकार वापस करें।

कोड

सी ++ प्रोग्राम एक क्रम में लगातार एक ही शब्द को हटाने के लिए

#include<bits/stdc++.h> 
using namespace std; 
  
int removeConsSame(vector<string > s){ 
    stack<string> st; 
  
    for(int i=0; i<s.size(); i++){ 
        if(st.empty()){ 
            st.push(s[i]);
        }
        
        else{ 
            string str = st.top(); 
  
            if(str.compare(s[i]) == 0){ 
                st.pop(); 
            }
  
            else{
                st.push(s[i]);
            }
        } 
    } 
  
    return st.size(); 
} 
  
int main(){ 
    vector<string> s = {"ab", "aa", "aa", "bcd", "ab"};
    
    cout << removeConsSame(s); 
    
    return 0; 
}
3

एक क्रम में लगातार एक ही शब्द को हटाने के लिए जावा प्रोग्राम

import java.util.Vector; 
import java.util.Stack; 
  
class removeSame{ 
    
    static int removeConsSame(Vector <String > s){ 
        Stack<String> st = new Stack<>(); 
       
        for(int i=0; i<s.size(); i++){ 
            if(st.empty()){ 
                st.push(s.get(i));
            }
            
            else{ 
                String str = st.peek(); 
       
                if(str.equals(s.get(i))){     
                    st.pop(); 
                }
       
                else{
                    st.push(s.get(i));
                }
            } 
        } 
        return st.size(); 
    } 
      
    public static void main(String[] args){ 
        Vector<String> s = new Vector<>(); 
  
        s.addElement("ab"); 
        s.addElement("aa"); 
        s.addElement("aa");
        s.addElement("bcd");
        s.addElement("ab");
  
        System.out.println(removeConsSame(s)); 
    } 
}
3

जटिलता विश्लेषण

समय जटिलता

पर) जहां n सूची में तार की संख्या है। जैसा कि हमने अभी स्ट्रिंग्स पर पता लगाया है, समय जटिलता केवल ओ (एन) है, जो एल्गोरिथ्म को रैखिक समय में चलाने के लिए बनाता है। लेकिन ध्यान देने वाली बात यह है कि स्ट्रिंग्स की तुलना की जा रही है और हमने माना है कि स्ट्रिंग्स की लंबाई कुछ स्थिर होती है जो N से कम होती है क्योंकि सबसे खराब स्थिति में स्ट्रिंग की तुलना में O (लंबाई) समय लगता है।

अंतरिक्ष जटिलता

पर) क्योंकि हमने n स्ट्रिंग्स को स्टोर करने के लिए स्थान का उपयोग किया है। जब भी वर्तमान सूचकांक में स्ट्रिंग और स्टैक के शीर्ष पर स्ट्रिंग समान नहीं होती है। हम स्ट्रिंग को वर्तमान सूचकांक में स्टैक में धकेलते हैं। सबसे खराब स्थिति में, हम सभी स्ट्रिंग्स को स्टैक में धकेल सकते हैं। इस परिदृश्य के परिणामस्वरूप O (n) स्थान की जटिलता होती है।

स्टैक का उपयोग किए बिना

कलन विधि

  1. की सूची को प्रारंभ करें n तार।
  2. सूची के 0 से आकार तक का पारगमन - 2।
    1. सूची में वर्तमान इंडेक्स + 1 पर शब्द के साथ सूची में वर्तमान सूचकांक में शब्द की तुलना करें।
      1. यदि दोनों तार अलग हैं।
        1. वर्तमान सूचकांक में वृद्धि
      2. यदि दोनों तार समान हैं।
        1. सूची से दोनों तारों को हटा दें / मिटा दें।
        2. जांचें कि क्या वर्तमान सूचकांक 0 से अधिक है
          1. वर्तमान सूचकांक में कमी।
        3. सूची के आकार को सूची के आकार के अनुसार अपडेट करें - 2।
  3. सूची का आकार वापस करें।

कोड

सी ++ प्रोग्राम एक क्रम में लगातार एक ही शब्द को हटाने के लिए

#include<bits/stdc++.h> 
using namespace std; 
  
int removeConsSame(vector <string > s){ 
    int n = s.size(); 
  
    for(int i=0; i<n-1; ){ 
        if(s[i].compare(s[i+1]) == 0){ 
            s.erase(s.begin()+i); 
            s.erase(s.begin()+i); 
  
            if(i > 0){ 
                i--; 
            }
  
            n = n-2; 
        } 
  
        else{
            i++;
        }
    } 
    return s.size(); 
} 
  
int main(){ 
    vector<string> s = {"ab", "aa", "aa", "bcd", "ab"};
    
    cout << removeConsSame(s); 
    
    return 0; 
}
3

एक क्रम में लगातार एक ही शब्द को हटाने के लिए जावा प्रोग्राम

import java.util.Vector; 
  
class removeSame{ 
    
    static int removeConsSame(Vector <String > s){ 
        int n = s.size(); 
       
        for(int i=0; i<n-1; ){ 
            if(s.get(i).equals(s.get(i+1))){ 
                s.remove(i); 
                s.remove(i); 
       
                if(i > 0){ 
                    i--; 
                }
       
                n = n-2; 
            } 
       
            else{
                i++;
            }
        } 
        return s.size(); 
    } 
      
    public static void main(String[] args){ 
        Vector<String> s = new Vector<>(); 
  
        s.addElement("ab"); 
        s.addElement("aa"); 
        s.addElement("aa");
        s.addElement("bcd");
        s.addElement("ab");
  
        System.out.println(removeConsSame(s)); 
    } 
}
3

जटिलता विश्लेषण

समय जटिलता

O (n ^ 2) जहां n सूची में तार की संख्या है। चूंकि हम वेक्टर से तार निकाल रहे हैं। वेक्टर टेकड रैखिक समय से किसी भी तत्व को हटाना। क्योंकि यह ऑपरेशन एन बार किया जा सकता है। समय जटिलता बहुपद है।

अंतरिक्ष जटिलता

ओ (1) क्योंकि हमने जानकारी को संग्रहीत करने के लिए किसी भी मध्यवर्ती डेटा संरचना का उपयोग नहीं किया है। तार को संचय करने के लिए एकमात्र स्थान की आवश्यकता थी, जो इनपुट का हिस्सा है और एल्गोरिथ्म के लिए अंतरिक्ष जटिलता की गणना करने में विचार नहीं किया जाएगा। लेकिन एक पूरे के रूप में कार्यक्रम अभी भी O (N) स्थान लेता है।